I'm a little worried about having a paladin in STAP
At the end of the campaign , if I understand well , the group will have to deal with demons to stop Demogorgon. I don't see a paladin accept this
First adventure ! "so an official says you didn't pay your dues and you don't have any proof , milady ? I'm sorry , I do believe you but I can't allow breaking and entering the ship giving the situation " . Ok , what you could do is having the paladin actually view the exchange of money some days before then he would know soller lies and it would help him take the law in his own hands in this particular case .
This resolves the first module but what about the end of STAP
Actually, the Paladin would likely not have many, if any, qualms, when the whole situtation from the ship is looked at.
First, a large part of Lavinia's story could be verfied elsewhere - her parents have died, her brother does seem to not be around, and, if the paladin has any sort of connections with the nobility, he could likely find out that many organizations owe Lavinia's family money - as she will find out in the vault.
In addition, a well connected paladin would likely know about the vaults.
Next, the paladin could fairly easily confirm that the Nixie is indeed the Vanderboren's family ship.
Third, it's fairly well known in Sasserine that the Harbormaster is not exactly paying much attention to the harbor, and that leaves the possibility of corruption on the docks.
But, here is the kicker for any LG PC.
Vark moves the ship.
A ship, under harbormaster impounding, is not to be moved. Not only does he move it, but he has people, and cargo, on board. While the Paladin would not know about the cargo initially, he can see the men on guard from the dock.
So, as soon as he gets to the dock, and sees the ship moved, he has to investigate, if he is playing the law and order type of Paladin.
Also, note that Paladin does not mean 'rigid, unthinking, can't use deception' knight in armor.
A paladin can sneak in a back door.
A paladin can use traps.
A paladin can snipe a badguy mage from 250 yards with a bow.
What a paladin can't do is evil acts - so your paladin is can't support a 'kill them first, sort it out later' approach to the Nixie. But, then, he doesn't have to.
Paladins' can be as flexible as any other class, if the DM allows it. Too often, it's the DM, not the Paladin, that limits the Paladins creativity.
And don't forget that part of the fun of being a paladin is that conflict between idealism and reality. If he can be convinced that a greater good can be accomplished by allying with a fiend against another fiend, he may do it without losing his paladinhood. However, it should be a very uncomfortable alliance and a wise paladin would always keep one eye over his shoulder to make sure his "ally" is holding up their end. Also, depending on the nature of the deal, pitting evil against itself may be just what he wants to do. He may weaken another force of evil by using it against his own enemy. And then it would be easier to come back and mop the floor with his expended ally.
However, the end is still a concern for the paladin. I would suggest having the paladin go off and try to convince some powerful forces of good to help while the rest of the party tried the demon princes, and then not ask them who they got to help them. This would in no way violate a paladin's oath.
I got the idea from a bbook, where a race of people was incapable of causing others harm, and grew slightly ill even considering the idea. They helped in a war by carrying sealed envelopes to various people, while refusing to hear what they contained, so they would be able to deliver battle plans.
One of my players will be playing a Paladin of Freedom (variant chaotic good paladin from Unearthed Arcana) in STAP. I agree, this is an issue of concern. I am running a homebrew campaign right now where this has become an issue. The character in question isn't a paladin but he a lawful good fighter/cleric of St. Cuthbert so it's very close.
To me, the central issue for many paladins wouldn't be that they couldn't work with one fiend to destroy another. If one demon is going to destroy the world and the only way to stop him is to ally with other demons, than I think even a paladin would do it. But there is one major caveat: if the potential ally required the paladin to do a service in return that was evil, then the paladin would not do it. For any reason. At least, that's the way I see it.