Shadowheart's entire origin story is intrinsically tied to her being a Cleric of Shar so if you respec her into a paladin then her entire story will no longer make sense.
I was in part joking, but in part not because there's not much difference between a cleric who adheres to Deity X and a paladin who adheres to Deity X in my view (or a warlock who adheres to Deity X, either, for that matter).
Shadowheart, Will, and Gale at least you should never respec into other classes. Though in general, respecing origin characters is a bad idea. If you want a Paladin in the party and you don't want to play one yourself you could recruit Minthara.
I assume it will not be possible to muiti-class companions, but let's pretend it will be, for the sake of discussion. In this hypothetical discussion, there is no "should" anything.
