Sorry to say, but NE would end up being the worst, simply because they have no healing ability (Tranq is worthless since there's stun for every race). Orc has Healing Wave, UD has Coil, and Human has Holy Light.
I'd have to go with Human, because you can't focus the Paladin, because 45 seconds of invulnerability is going to keep that from happening while he heals. To go along with him using mana, he'll get a continuous supply of mana from the Archmage, and focusing on that? Holy Light of course. Also, you can't hero-nuke a MK in Avatar as he's magic immune not to mention Storm Bolt, and Bash, oh, and Siphon Mana/Banish will put heroes out of the match.