The answer depends largely on what your concern with the balance around this character is.
Too much HP?
If you have a quarrel with the level of HP the character has rolled (his HP is very high), then you can change the battle tactics of the enemies to address this. If you start introducing more complex battles that have multi-tiered combats, this HP will be whittled down, especially as his character will likely be taking the majority of the damage.
As you all enter the large chamber, you see two robed figures across an 80 foot pit each holding a sling and a vial of a strange goo. The only way across is a rickety bridge on the far left side of the room. Roll initiative. (You roll initiative for the two goblins while secretly have initiatives prepared for other creatures not yet visible by the PCs). On the first figures turn he hurls a rock at a pressure plate near the ceiling on his side dropping an orc into the chamber separating the front liners who have begun to work there way to the bridge from any healers in the back, the orc uses a readied action to attack the paladin approaching the bridge. Later in the round the other figure pours some goo onto a stone and hurls it at long range at the ranger with disadvantage. The stone misses but when it strikes the wall a small explosion goes off blackening the stone wall behind (this is a way to show them what the goo does but at disadvantage so you don't punish them early on for not knowing). The Paladin may not want to try his weight on the rickety bridge so instead he climbs down the wall into the pit but once he enters the pit torches above each side blast flames covering his way out and a gate begins to open on the right side, a foul odor entering the room (ala Rancor Pit). If he does walk on the bridge it breaks, prompting a Dexterity check to catch the fall putting the character in a treacherous position anyway.
This type of combat is not only more fun and memorable to most people, it is a way of dealing with clunky but bulky melee characters without making it seem like you are focusing them too much. His actions got himself stuck in the "Rancor Pit".
Too much AC?
With bounded accuracy in fifth edition, every additional point of AC can be very powerful but most creatures can still deal with the player. Even so, 20 AC can be harrowing to a lot of encounter structures. One way to fix this problem while keeping the feel of the character is to use magic items. A shield gives +2 AC while wielded, so introducing a two-handed weapon that has a unique magical property give the player a choice between the added defense and the additional power. In my experience, players are more likely to use the fun magic item then to just write +2 on their stat-sheet.
This magic item doesn't even need to be powerful. Here's an example of a way to spice up the system based on the encounter from the previous section. After the paladin roughed his way through the mutant umber hulk with the help of the wizard from above and the rest of the party had cleared out the room, the paladin sees a greataxe back behind the hidden gate that had opened before. It glimmers with a sort of gold hue. When you lift the axe the fires that had trapped you in before glow blue and lose the heat they had once held before. On the cheek of the axe is the holy symbol for Gond the god of craft. An identify spell reveal that when wielded by a holy character (paladin, cleric, or some subclass like divine soul) the creature is resistant to fire damage and can move through non-magical fires unharmed. Additionally whenever the character takes fire damage from an enemy, the axe gains charges which can be used to deal an additional 1d10 fire damage with a melee attack (charges reset to 1 at dawn).
This type of weapon is a fun way to give the paladin another option than strict defense. Further, its limit on fire damage lets you decide how powerful it needs to be by limiting how many creatures deal fire damage.
Too much Mobility?
If the combo of movement speed and misty step makes the paladin too able to close in on your casters and ranged attackers during combat, give those creatures other options either with further mobility or spells like cordon of arrows. This will make the paladin more weary about jumping into the back-line so aggressively. If the issue is holding the paladin down during an important fight or story moment, the arch-wizards golem can always grapple him forcing misty step only to be counter-spelled by the wizard leaving the paladin helpless without the aid of his party.
There are countless options that are similar to these that give story opportunities and fun features without limiting the players options. With proper employment of engaging activity, a DM can adjust balance of players' items and fighting styles. It's simply an extension of the "yes, and..." policy.