The Witchking certainly had spells (crashed the gate of Minias Tirith with the help of one). Maybe some higher ups from the orcs as well. As some of them were even Maia in origin (Boldog) they could possibly make such things happen, as they had greater understanding of the nature of Magic, compared to the common orc and men.
And then there is Beorn, who could shapeshift into another species (that is comparable to a powerfull spell). And then we have the Druedain with their stone figures.
Would be interesting to know, if anything is known about the Haradrim or Easterlings on the power of spells?