She tried to! She tried to have him burned alive as an offering.
Image source
Jon didn't approve, and intervened, mercy-killing him with an arrow before Mel's flames could.
It's not explicitly explained, but it's strongly implied that to do the "summoning shadow murderer guy" trick, she needs to have sex with someone with king's blood and a certain amount of "strength", which she'd drained out of Stannis when using that trick against Renly.
It's fair to say Mance probably wouldn't have been up for that, hence the burning instead.
As for Gendry, well, you're assuming she was doing magic when she threw those leeches into the flames... We don't have firm evidence either way, but consider which is more likely:
- Mel can kill anyone, anywhere, with just a leech's worth of vaguely royal blood, but only does this once, and never does it against foes who present an immediate threat.
- Mel foresaw the deaths of those three characters in the flames (using powers we already knew she had), and used this as part of a trick designed to increase the faith of Stannis and others by taking credit for things she knew would happen anyway (in exactly the way she confessed to Selyse that she does use:
...lies. Deceptions to make men think they witnessed our Lord's power. ...a trick that lead[s] them to the truth
We see in Season 5 that Mel burning people alive seemingly can reap rewards (unless that was another thing she foresaw and took credit for - but if so, surely she'd have done something less controversial to take credit, like re-using the leeches trick?) - so presumably Mel was expecting an effect similar in magnitude to the snows clearing. When prevented from doing this with Mance, she found someone else...