When I reach Selwyn's tower, I can only find Selwyn, the pirate, and the fighter. The paladin seems to be missing. I have tried to reach the tower from multiple save points and even time stopped to check to see if the paladin was sitting at his proper place at the upstairs table. In fact, the pirate was in his place. Is this a result of a bug?

Not a bug I've seen before, but anything can happen I guess.
I'm using Exult, and it shows his NPC number is 288. Not sure if the number is the same in vanilla, but it's likely the case.
You might be able to teleport to him through the cheat menu, so to find out where he is. I'm not entirely sure if teleport to NPCs is an option in vanilla though.

Also check out if he might be sleeping in the bed downstairs. Who knows.

Gotchas tip is perfect and should work. teleport to an NPC number will work in Vanilla and Dosbox installations as well as in Exult.

The teleport suggestion worked. I found the missing NPC on the roof of one of the buildings in Britain. I have no idea how he ended up there.

The Imbalance started early in your game; must've been a teleport storm. :P

Just the cheat room roof in Trinsic.