No, you ignored the actual questions.
Have i tho?
Ok ... lets see.
How would a devotion paladin Astarion work considering it was his job to lie?
I repeat my answer:
Who said the he WAS paladin all along? You can sworn an oath any time you want.What i mean by this, is that we dont change Astarions story, just his class ... and we dont change his class retrospectively, but at the moment.
By making Astarion a Paladin, i dont say he was Paladin last 200y ... i claim he IS paladin ... like *now*.
But i also can offer alternative answer ... 2 things:
1) It was never his job "to lie" ... and if you wish to claim otherwise, i challenge you to show me your source.
2) Even if it would be ... "to lie" and to "not tell everything" is very important difference, that serves as easy workaround to writers for several last decades ...
"I would like to introduce you to somebody."
"Maybe you would like to follow me to some more ... private place?"
"Sheesh, this party is boring ... wouldnt you like to try something more exiting? I know about some place."
See? Neither is lie ... all of them is luring a victim to his master lair.

THAT is how Astarion would work as an Devotion Paladin.

He also would not be able to lie in any of the cutscenes and dialogues (same would apply to devotion paladin Gale with his tales or devotion Shadowheart?)
And wich one of them do?

And when?
Since as far as i know, the dodge subjects, and refuses to talk a lot ... but they dont lie.
For respeccing to work no origin companion would ever be allowed to use or reference any class ability in a cutscene or dialogue, in a game. No bear scene from Halsin because he might nit be a druid at that point, no display of magic from Gale at any point ect.
Again ...
You made same misstake as abowe, by respecing someone Class, you dont erase their history and whole life to this point ...
Gale still was a Wizard ... some time ago ... he is just not anymore.
Halsin was still a Druid ... some time ago ... he is just not anymore.
Im sure someone will ask how can anyone "stop being a Druid" ...
I dunno, and since its not cannonical part of their personality, neither will you, since it wouldnt be possible to talk about it with them.
Maybe Oakfather got pissed on him, maybe something went wrong and he decided that he will never ever again take another wilshape ... feel free to make your own headcannon, it dont matter anyway.

And the question about Shadowheart was not about respeccing her into another class (but that too can be problematic, see the devotion paladin) but resoeccing her into a cleric of a different deity.
Hard to worship shar if you are a cleric of Tyr.
But you are not becoming Cleric of Tyr ...
What you are respecing is a Class ... meaning Cleric ... nothing else.
Just as Lolthsworn Drow cant become Cleric of Tyr ... they have to worship Lolth.
Just as Githynki cant become Cleric of Tyr ... they have to worship Vlaakith.
Just as Duergar will most likely be unable to become Cleric of Tyr ... they will most likely have to worship Laduguer.
Those are locked options.
Same apply to Shadowheart ...
Shar is locked on her, bcs that is what her story require.
No matter class, Shadowheart WILL worship Shar.
If Shadowheart will become Devotion Paladin ... she will be Devotion Paladin, worshipping Shar.
If Shadowheart will become a Wizard ... she will be Wizard, worshipping Shar.
If Shadowheart will become Cleric again ... or just change subclass to become different kind of Cleric ... she will be Cleric of Shar.
Yes ... even if she would be Light or Life Cleric, wich is allready possible and its two weirdest combination you manage to squeeze out of it.
For all this to even remotely work the story of those characters would need to be grinded down to the most generic, cookie cutter thing imaginable. Or Larian has to do extra work to make cutscenes for every eventuality. And both are simply not worth it.
Both are also not true.

It only need to open your mind a little.

Now ... will tho answer my questions?

(Said with Withers voice.)