Stimmt so nicht ganz. In den Realms muss zwar jeder göttliche Zauberwirker einen (und zwar genau einen) Patron haben, in den Core Rules steht aber drin, dass man eigentlich überhaupt keinen Patron braucht, sondern auch irgendeine universelle Philosophie als "Gott" haben kann. Insofern wäre es durchaus möglich, dass ein Paladin in erster Linie dem Guten dient, eine Vielzahl rechtschaffen guter Götter anbetet.
Insgesamt wäre ein Zweihänder bestimmt eine passende und sehr gute Waffe, wenn du dann noch Power Attack und Divine Might (DotF) nimmst, kannst du schon ziemlich viel Schaden austeilen (vor allem mit Smite Evil!). Der Templar bringt dir die Waffenspezialisierung und ist insofern ziemlich gut.
Ich würde später noch Power Lunge (SaF) nehmen, das es dir erlaubt, bei einem Charge den doppelten STR-Bonus auf den Schaden anzurechnen. Ein sehr gutes Feat, außerdem hast du Power Attack ja schon.
Mit Power Attack und Smite Evil könntest du auf der 1. Stufe mit dem Zweihänder schon 2d6+9 Punkte Schaden machen, was sehr gut ist. Auf Stufe 3 kannst du mit Power Lunge bei einem Charge mit Smite Evil und max. Power Attack dann schon 2d6+17 Punkte Schaden verursachen. Auf der 6. Stufe könntest du mit Divine Might, dann auch noch deinen Cha-Bonus auf den Schaden addieren - für ganze 2d6+30 und das mit einer nicht magischen Waffe
CHA und CON tauschen würde ich auf jeden Fall auch machen, CON 16 reicht völlig und ein Paladin kann nie genug CHA haben.