The rules for moving the paladin are the same in the Combat and Building Phases. You have to check the situation after each move on the Evilometer. (Players never move their Evil Counters simultaneously.)

The paladin enters the game as soon as a player’s Evil Counter gets on or above the marked paladin space of the Evilometer. He is put in front of that player’s dungeon. He moves to another dungeon only when another player’s Evil Counter is:

• “on or above the paladin space”

and at the same time:

• “higher than the Evil Counter of the player who currently has the paladin”.

Especially note:

• The paladin does not leave when the player’s Evil Counter falls below the paladin space.
• The paladin does not move to another player’s dungeon if that player’s Evil Counter is not on or above the paladin space (even if that player is more evil that the player that currently has the paladin).
• The paladin ignores the Starting Player Token (if Evil Counters are tied, he stays where he is), unless two new players become most evil (and on or above paladin space) at the same time. (This can happen when the most evil player drops and exposes two other players to be most evil, or at the start of the Second Year, when a new paladin has to be assigned.) In these cases only, the paladin goes to the player that is last in play order among the tied players.