If you want to make a two handed beater character with good saves would pure paladin do the job well or should some other classes be mixed in as well?

A Paladin would do the job well enough on its own. That said, especially in the case of melee classes, multiclassing would make it stronger. In your case, a Paladin with some Two-Handed Fighter levels tend to be the most common example spammed around.

That said, for my money, the Crusader path for the Cleric is like a Paladin that out-Paladins Paladins.

For almost any none caster build you will want 1x vivisectionist and 1x rogue for the sneak attacks + the sneak attack feat, which gives you 6 rogue levels worth of dps.
If all you are after are the saves then 2x paladin is enough and you could 2h warrior or something for the rest.
I would also add 2x scaled fist (cranestyle) and go unarmored once i got +5 bracers, + char head item,. and a decent robe.
With 16 base charisma that will get you more ac then anything you could get with a full plate + shield.

Curious which order you would take the levels in and which race(prob angelkin aasimaar?) and also how you would put your ability scores. :)

Angel asimar would be my 1st choice. As for the order of levels, I would take classes with full bab for the first 6 levels just to get that extra attack asap before dipping into vivi / rogue, but other than that it does not matter much.
For stats i would aim for 14 con/dex and atleast 16 char while dumping wisdom (unless you are going more than 2x paladin obviously).
As angel asimar you should be able to go 18str ,14 con/dex, 12 int, -7wis, 17 char if i am not mistaken, which would be pretty optimal for that build.

18's and 7's Aasimars.

Blech.

More like Ass-imar. Minmaxing is usually inelegant and ugly, but some are worse than others.