I'd seriously considered taking Resilient (Constitution) - many paladin spells are Concentration and your character is set up as a front line fighter, so you'll be taking hits.
After the most recent ruling, Shield Master is still good, but probably not worth it until lvl 11+ when spells like Disintegrate become more common.
Sentinel really depends on if you are going to have other characters adjacent to you (so you get a free shot if the enemy attacks them), or if your DM has enemies move away (thus provoking) for tactical reasons frequently or not. If the bad guys just walk up to and stand there attacking the most heavily armored guy in the party...it's not that great a feat. If they are constantly trying to get past you to target the squishier members, then it's fantastic
That's another question. How often do paladins cast spells in 5e? By reading around, I thought that spells are mostly used for smites and just a couple of spells. Are "casting paladins" viable?
Yes you would be fine with 18 Cha. I'd max Str for sure though.
What is the rest of your party? That'll determine whether or not Sentinel is worth it. My favorite part of it is getting a relatively reliable reaction attack. If you have any other melee character, you just go fight beside him. He benefits too from your Aura of Protection. I'd skip Shield Master.
I don't think we are the best party there is out there. Barb-Pally-Warlock-Sorc.