Orc Mage - they have warlocks in lore, meaning they have affinity to magic (lore-wise, Warlock is a Mage who uses his powers to summon and enslave demonic beings)
Dwarf Shaman - dwarves are rather close to nature, living in the mountains close to the element of earth. Also, rememebr the Wildhammer dwarves, who have an even closer bond to nature.
Night Elf Mage - according to screenies from PTR, the Highborne are making their return. Originally, Night Elves were skilled magi (and warlocks too, tbh), they forsaken their magic for fear of Burning Legion's return. Now that the Legion has access to Azeroth anyway, why should they forfeit such a source of power, as arcane magic?
Goblin Shammy - they were originally a spiritual race, slaves to the jungle trolls of Kezan. they might have learned something from troll voodoo. Also, the ore that gave the goblins their intelligence was used by trolls in voodoo rituals.
Tauren Paladin (as well tauren priest) - Light and Shadow are both spiritual disciplines as well, with the Holt Light associating with the Sun, which is a major diety in Tauren pantheon (Eye of the Earthmother)
don't see any problems