I'd be tempted to just give him a character rebuild when he's accepted into the order, and just let him trade in some or all of his Cleric levels for Paladin levels. Especially if a god's representative is involved in the transition: "You have faithfully answered the call of ministering to my flock. But now you have a new calling, and I bestow upon you power to befit your new role..."

Or let him stay straight Cleric: knighthood and membership in the order is a social status, there's no reason that has to be restricted to people who have Paladin class levels.