Even in Combat, the paladin can move to another player, following the general paladin rules. If he moves, he takes all the damage he received so far with him.
Note that Battle is evaluated in clockwise order, beginning with the starting player (i.e., the player that was starting player in the last round of Building). In some cases, this order can influence whether the Paladin moves, to which player he moves, and also whether he will affect Battle again this round.
When the paladin moves to a different dungeon, it results in one of three cases:
If the paladin is eliminated, he goes to the prison of the player that assigned the last point of damage to him (even if another player assigned more damage before the paladin moved). There will be no paladin for the rest of the Combat, no matter how evil the players are.
If the paladin is not eliminated, he leaves to the Distant Lands Board at the end of Combat.
So after First Year Combat, the First Year paladin is out of the game whether he was eliminated or not. If at least one player is on or above the paladin space of the Evilometer at that time, the Second Year paladin is assigned at the start of the Second Year (after the Starting Player Token is moved).