Unfortunately Barbarian and Paladin are not a good multiclass combo, and pushing 2 attacks per round from level 5 to level 8 will be painful for fighter classes as leveling tends to slow down after 5. Traditionally Paladins match best with warlock, bard and sorcerer. Barbarian would be good with Druid, but that combo is not usually built on charisma so will be more difficult to be the face of the party.
Honestly the Paladin does not even require to be multiclassed as its one of the most powerful classes in 5E. If you want to multiclass the pally I would recommend starting as paladin to level 6 (7 for Oath of Ancients) and then take a dip in your other class if you were looking for more abilities or spell slots. Level 6 paladin gets you the aura so that's typically the must have level for pallies.
