I think you're kind of typcasting paladins a bit here. Astarion is an unrepentant vampire who seems like he would be fine being a vampire if he just didn't have to obey his master, so he'd be bad for a paladin, yes. Lae'zel is also ruthless and brutal and uncaring in a way that a paladin would certainly object too, I agree. Shadowheart as you say, does have some room to potentially become good, especially since you don't find out the truth until a while in, so there's a chance to make a bond there. Wyll made a deal with a devil, but he does want out and he has tried to do good and seems like he could be a genuinely good person with some support. I think it would be easy to justify a paladin wanting to help him break free of his deal and redeem him. Gale is unstable and a potential threat, but that threat can be mitigated in a very clear way and beyond that he's, from what we've seen, a perfectly unobjectionable person. Is he kind of shifty and probably untrustworthy? Yeah, but not to a degree that a paladin would feel the need to get involved with, I don't think. If anything, a paladin would want to help him be free of his curse to try and protect people, since I don't think paladin's are meant to be a kill first, ask questions later sort of group.
So yeah, it's not truly that hard to justify a good party. Lae'zel, Astarion and maybe Shadowheart are the only ones who would be definite no's.
