You're employing an entire god to screw the player over. Don't do this. It's not fun.

At minimum the paladin wouldn't be the first and there would be some kind of larger plot for him to discover with other paladins and clerics getting screwed over first. The deity shouldn't even be interested in the paladin individually unless he's level 15+. If not level 25+.