Orcs have had their time on Azeroth and since they have been part of Argent crusade they should have been around to pick up the priest profession. HOWEVER orcs could have their priest lore stem from the Bleeding hollow clan. This clan had all this blood sacrifice stuff and peeking into the darkness to witness fates. They could be driven lore wise primarily by the shadow priest spec, just like the Forsaken. Orcs taught the ways of divination of the Bleeding hollow clan could now decide whether to align with the light or darkness.
Also I would like to add that even though orcs were shamanistic and worshipped the elements, orc priests have understanding of the TRUE primordial forces of the universe, light and shadow.