As written, Bluff is the only appropriate skill.
You can make what’s false appear to be true, what’s outrageous seem plausible, and what’s suspicious seem ordinary. You make a Bluff check to fast-talk a guard, con a merchant, gamble, pass off a disguise or fake documentation, and otherwise tell lies. (PHB1, p183)
Since the party would be attempting to "make what's suspicious seem ordinary" and use social fakery, Bluff is the right ability. Diplomacy is for tact, good faith, and etiquette; Streetwise is a knowledge skill; Stealth is for physical rather than social situations; and Thievery is even less a social skill than Stealth.
But don't hold to that too strictly: allow creativity.
I've found it's very helpful to allow the players to attempt to justify any skill as appropriate to a skill challenge. Takes some of the pressure off me, makes the challenge (and the ensuing story) more interesting, and engages the players more in the agency of story-telling instead of my telling them the only ways their story can be told (by pre-selecting the skills in the challenge and only allowing those skills).
For example: Streetwise could be used to know more about what makes one "ordinary" in that town. Diplomacy might be leveraged to make friends in high places whose social weight would make the police less likely to "randomly" target the party. Stealth could be used to avoid the police entirely, while Thievery can be applied to more effectively conceal or ditch any secret items.
If the proposed non-planned skill is allowed, allow it without penalty; there's no point in penalizing a player for being successfully creative, unless you want to discourage such participation in the future.
[Tangentially, I used Stalker0's Alternate Core Skill Challenge System to great effect; it's a bit more mathematically balanced than the original system, and has great structural ideas you might find useful (they appear in some individual 4e skill challenges in pre-made adventures, but here are institutionalized in the skill challenge system itself.)]