You could always do a Cleric dip. It costs a hit to your charisma, but getting war or tempest cleric ups your spellcasting and gives you some bonus damage as an extra attack or reaction, respectively. It will also let you get guidance on your MC which is helpful when talking to SH, since she won't use it against herself. Also if you pick a lightning type dragonborn, the tempest fits thematically. It's rough, but doable.
Stats would be:
Str 16
Dex 8
Con 14
Int 8
Wis 14
CHA 14
with a point for Int Or Dex, your choice.
Honestly your spell slots are mostly going to be for smiting anyway, so having weaker offensive spells isn't quite as huge of a deal as it could be if you were focused on spellcasting. You'll probably just throw out bless or some other concentration spell and hold a slot or two back for emergency healing. If you go with this build, you may even want to just go Paladin 5 (for extra attack) or 6 (for aura) and do everything else in Cleric to get the extra spell slots. 6 Paladin + 6 Cleric gets you a bunch of higher level spell slots that can only be used for upcasting or smiting (3 level 4s and one level 5). 5 Paladin and 7 Cleric costs the Pally's aura, but gets you the 4th level Cleric spells instead of just slots.
This is basically a slightly 'worse' Paladin Bard build that you see out in the wild because of the points 'wasted' on Wisdom. However, Insight is hugely important in BG3 so the tradeoff in power level actually pays off in roleplaying.
Note: I would start Pally, as you can get cleric at level 2 right off the ship. It gets you a couple extra HP and better starting gear. I'm not sure if SH has a Shar convo on the ship, but I doubt it, so you wont miss anything. (someone please correct me if I'm wrong).
Oooh I do like this plan. I also have one fighter/cleric build in mind but I was planning on using it for a "good" playthrough where I basically go 2-3 fighter/ x light cleric but I could change it up and leave the paladin for another playthrough as well.
Also, I've been considering 6 Paladin/6 cleric for a while, specifically to get a smiting spirit guardian tank which sounds amazing to me... but wouldn't that be relatively weak for late game? Considering I would have a bunch of medium power feats/spells, but nothing from high-levels at all.