not going to go over everything related to the paladin but i'll cover some stuff and add some things about the shadow mage and some of your other more off topic suggestions.
1. You want to be a tank yet you are statting strength ok... first problem. str for paladins i believe gives 1 atk dmg vs 1 point in con which adds 30 hp and unlike atk there are 2 party buffs which give 15% additional hp for a total of 30% poppets not included. So whyyy are you statting str?
2. over time your defense will over take a shadow mage due to warrior/paladins armor having higher defense, dodge, and magic resistance. A shadow mage also uses pots like crazy i use non stop mp pots because i chose to not stat wis, if you had more con
the hp regen would help reduce the amount of hp pots you use. In the end with 33+ mobs a shadow mage cant really tank all that many mobs anymore 2-3 silvers and i just run, its way too mp intensive to heal non stop.
3. The main issue with pve balance comes from the lack of incentive for people to join parties. If there was a party mechanic that increased exp etc. to that of what one could do solo then a lot more people would join parties. Even now my shadow mage actually only slightly makes more gold/exp solo than when i am in a duo with a warrior and that is because unlike most sm i took deaths cauldron to increase my aoe dps.
4. Honestly lower the cooldown of heal for paladin from 3 minutes to 1 minute and tweak their aggro abilities further and maybe give them a passive def buff and they would be fine. Their tanking abilities aren't that bad right now and in max gears i expect paladins will have a possible 8k+ hp. and their main job in pvp is support which is like any other game.
5. As far as runes are concerned yea it sucks but seriously all mmo's are like that otherwise everyone would be in max gears in a couple of days and what would be the point.