As such, I think my two challenges are going to be "give him a reason not to turn the dragonborn paladin PC's bones into molten metal" and then "prove that you're useful enough to him that he won't chain you to a burning iron grate."
I'll want to dwell on pride - in appearance, accomplishments and power, I think. He'll be very interested in history, and has a task that the PCs can do in exchange for living. Heck, he'll even reward them for it, or grant them infernal power. This thread is giving me some good ideas on how to accomplish that.
I'd make it three challenges... Two short ones (like you suggested above) that are apparently scary, but ultimately easy and one that is longer, outwardly safe, but far more dangerous on a long term scale, like so:
Challenge #1: "Why shouldn't I kill you now?"
Challenge #2: "What use are you to me?"
Challenge #3: "Talk to my lawyers, and they'll work out the details of the contract."
The PCs are transported to Hell, were they have to negotiate the conditions of their contract with one of Cenox's infernal barristers. This helps you in a couple of ways.
First, it gets Cenox out of the scene fairly quickly. He's far too powerful for the PCs, and you want to get rid of the temptation to fight a Lord of Hell ASAP. Likewise, once the PCs have "agreed" to work with him, there's no need for him to take valuable time out of his schedule to putter over the details of the paperwork... that's what he's got imps for.
Second, it puts the PCs into a situation a little more appropriate for their level, but still dangerous. They obviously won't be able to fight their way out of the hells, but will be sent home safely* once the contract is finalized.
Third, it provides the opportunity for long-term Rat Bastardry... The success of that third challenge would determine what the final contract looks like. If the players aren't paying attention, or do poorly during the skill challenge, the contract could end up lousy with fine print, terms, conditions and loop holes the consequences of which might not show up until much, much later in the campaign.
*If you wanted to add a fourth skill challenge and add just a smidge of comedy, have one last skill challenge that involves the PCs trying to find their own way out of the labyrinth of demonic "office cubicles" that they find themselves in, based on the elaborate directions the imp-lawyer has given them.