If it's a NPC, you don't even have to follow the rules. Just make a Cleric/Paladin and use Wis for the Paladin stuff too. I made a NPC Bard with a 22 Cha once, and I don't think the world ended that day lol.
If you want to play by the rules, which is understandable, I like the Fighter/Cleric idea. It's much easier to pull off and would be a really good character.

Start Fighter 1 for Con saves and then take at least 5 straight levels of Cleric. Vhuman could start you with 16 Str, 14 Con, 16 Wis, and the PAM feat and choose literally any Cleric domain since you already have heavy armor. You'd eventually want 5 levels of Fighter and you really don't need any other feats so you could just take turns bumping Str and Wis. If you think this character won't ever get past tier 1 or 2, Just be a high Wis Fighter with a small Cleric dip.

I think War Priest is really good at level 1 and 2, but then falls off quickly starting at level 3 and eventually becomes forgotten. I can think of several possible ways of making it better, but I'll save that for another thread.