Exactly, but I think the parodistic element is important as well. We expect (both from all the similar stories about genies and all the less wrong posts about what genies can be trusted) that he made a seemingly useful wish that backfired, presumably in a humourous manner (like how "The building explodes and your elderly mum is blown into the sky" is humourous, in a slapstick manner). We think he's going to ask for something he wants, but instead gets something he doesn't want, when he instead asks for something he doesn't want and gets it.
Also, you're obviously right when you think of "King Midas is starving to death. How? Magic." has no clear genre. It's a morality play about wealth and not making stupid wishes if the answer is "He used magic to wish for all he touched to turn to gold, not realising this meant his food as well. Being unable to digest gold he started to starve." and a joke if the answer is "He used magic to wish to starve to death. What a maroon!" Also, regarding OP, just making the answer magic is as silly as "Why is that man wearing a suit? Economics" and "Why is King Midas starving? Biochemistry."
Speaking of things that are funny to some and not others, an instructive example is the Orange Head joke. Usually when it's told, the audience is sharply divided into those who think it's hilarious and those who struggle to see what's funny.
Here's the Orange Head joke:
Do you think it's funny?
If you search for this joke's key words, you'll see many pages where, after it's told, people react incredulously and ask where the joke was. Others at the same time are laughing their heads off. Here's a blog post that attempts to analyze this, though it doesn't get far.
(I personally think it's hilarious, and easily the best joke I heard last year. When I retold it at my blog, I got many concurring comments, but also comments from people who didn't see anything funny, even after those who did tried to explain what they found in it. Several people went on to convince themselves it's garbled and there must be an "original" version in which the final remark makes sense and is funny - and offered several ideas of how it might go).