Well, you make a 4e-style Companion by following the back-of-MM re base stats model. What I tend to do in addition is remove spellcasting & replace with a subset, so eg my 5e Companion Paladin can Bless, Smite, & Lay on Hands, but not the full Pally spell range.
You can select a small number of Classic Cleric spells, eg Cure Wounds, & Thunder-related spells, plus a class ability like Turn Undead, give him those and call it a day.
The Paladin Companion IMC:
Malenn, Paladin of Mitra
Cohort (lover) of Hakeem.
Human
Armor Class 17 (+2 DEX +2 shield +3 CHA)
Hit Points 56 (9d8 + 18)
Healing Dice 4 (d8+2)
Speed 30 ft.
Proficiency +3
STR 8 (-1) DEX 14 (+2) CON 14 (+2) INT 11 (+0) WIS 13 (+1) CHA 17 (+3)
Good saves WIS, CHA.
Senses passive Perception 14
Challenge 3 (700 XP)
Divine Sense: 4/day she can focus - as an Action - & detect supernatural celestial, fiend or undead within 60', but not mortal alignment. Can detect consecrated or desecrated ground.
Brave. Malenn has advantage on saving throws against being frightened.
Unarmoured Grace. Malenn adds her CHA bonus to AC when unarmoured.
Duelist fighting style. +2 damage with single one-handed weapon.
Actions
Multiattack. Malenn can make two melee attacks.
Blessing of Mitra 6/day: Recharges after Long Rest - requires prayer to the rising sun to recharge. Action, requires a sprinkling of holy water, affects up to 3 willing allied creatures within 30'. In the next 10 rounds whenever the Blessed allies make an attack roll or a saving throw they add +2 to the roll. A creature can benefit from only one Bless die at a time. Requires Concentration - this effect ends if Malenn is incapacitated.
Alternately she can use the same energy to Divine Smite on a hit for +2d8 radiant damage, +3d8 vs undead or fiend, this does not require holy water.
Lay on Hands: She can touch someone and restore up to 30 hp per day (or spend 5 hp to cure disease/poison). Recharges after long rest.
Weapons (2 attacks/action)
Bronze Shortsword ATT +5 dam 1d6+4 (+2d8 smite)
Unarmed ATT +2 dam 0 (+2d8 smite!)