How exactly is the Paladin able to contribute to that goal?
Virtually anything he does. Quite simply, party+paladin is more powerful than just the party under most any circumstances - even if he were just a minion! (Ok, maybe not with cleave.) It's only scenarios where the utmost stealth is required that the paladin would be a liability, but then so would the party cleric. Since bluff was mentioned I don't think that's the case here. Astral Speech gives bonuses, for example. The paladin also has healing abilities. The actual answer to your question is so trivial that I'm not sure what you were getting at. The mechanics of the skill challenge allow a lot of flexibility in the player getting to define how he's useful.
If combat happens how does a character who normally uses heavy armour play his usual role?
The same way he always does. Again, if combat happens then I don't see how the party is better off without the paladin. He's not at his best, but short of him attacking the party I don't see how he fails to contribute. IMO I think it takes some class and maturity to suck it up, get through the adventure, and see the wider goals and chances for the other PCs to shine as something beneficial. It's a sort of enjoyment of the game that's not based on instant gratification and ego-stroking, but I think it's an important thing to learn to appreciate *especially* in a team-type environment where various people are bringing various skills to the table. Like in sports, music, or many other facets of life, sometimes the circumstances favor your talents, sometimes they don't. Trying to design around this issue IMO makes the game too antiseptic and transparently a DM-Player exchange without an versimilitude.