Paladin simply needs a single trait that both:
a.) rewards STR as attack damage (much more significantly than the existing 2str =1atk for all classes, while still balanced below the benchmark DD's) and ..
b.) rewards VIT as -dmg% taken based on enmity (understandably this should only be a small fraction of a percent per VIT point, and maybe drastically curve off towards an established VIT cap). VIT should also be rewarded as: 1VIT = 0.5HP (i.e. 100VIT = +50HP). Lastly, VIT should effect enmity as a reduction in enmity-loss while damage is taken.
Both of these could be contained in a single trait called "The Will of Mount Ordeals" obtainable at Paladin level 95.
I'm stretching a bit by combining four effects into one trait (attack+, -damage% taken, enmity-loss reduction, and HP+) but anyone who knows the condition of Paladin will know it's in desperate need of change. The added damage would help compete with the existing DD's enmity, and the -dmg% reduction would somewhat justify turning the monster. In thinking about this for a long time, I also wanted to somehow see AGI improve Subtle Blow, but this new added TP feed should be justified through the damage mitigation and enmity-loss reduction i'm proposing. Besides, it's just not fitting that a paladin strikes lightly, he's a big wall of metal ^^.
If a single trait here is too unbalanced, i'd say the only other option would be to have these as active aura's (STR or VIT) that can be toggled between the two (sort of like Hasso and Seigan, but no timers). No animation would be needed if it impacted the PS2, just a buff icon.
As a side note, if there was one other valuable suggestion for Paladin that I've seen on these forums over the the last month or so, is to improve Cover. There's been lots of proposals here, i.e. span the effect acroo multiple players/alliance, or automate during certain party members hp%, etc - all good suggestions.