I like to remember that "Paladin" is a job, not just a class. If you're recreating Anomen, I think doing a straight War Cleric is pretty good, with him aspiring to become a Knight of the Most Noble Order of the Radiant Heart; he doesn't need to have the class paladin. You might give him the Martial Adept or Fighting Initiate feat to emphasize that he's a warrior.

(You could also do with something like my Crusader subclass for fighter)