Overlord stays in play until Clean-up of the second turn. For ease of understanding, all those rules tell when to discard a card (like an Overlord or Throne Room or Duration card, for which special rules apply). From my understanding, the actual rule is "negative":
You discard every card in play during Clean-up, except
1) duration cards that have things left to do after this turn, or
2) cards that played a duration card an extra time and that duration card will be in play after Clean-up's discard effect, or
3) cards that played a card leaving it where it is out of play, when that card would be in play after Clean-up's discard effect.
So the question when to discard Overlord comes up during first turn's Clean-up, when it is not discarded due to rule 3), which is in effect because of rule 1), for Highwayman. The next time the question comes up is during the second turn's Clean-up. Then Highwayman would not be in play after Clean-up's discard effect, so rule does not kick in and Overlord is discarded then.
Since the usual time cards are discarded is during Clean-up, that's what the rulebook rule says.
The above rule also answers your second question in the affirmative. During the first turn's Clean-up, Captain stays in play because of rule 1). During the second turn's Clean-up it stays in play due to rule 3), because the Throne Room would not be discarded due to rule 2), because the Caravan is not discarded due to rule 1).
As you can see, those rules are recursive. In order to decide if some card is discarded or not, you need to check if another card will/would be in play after the discard effect, which may need to know the same thing about another card, a.s.o. Until now no loop for such dependencies seems to exist.