It’s a shame blizzard wastes their time with dumb sh!t like “Balance Patches” “Hotfixes” and “Expansion Development” and less time fleshing out the lore on how Orcs became mages.
A true shame.
But it seems like it’s mostly as I suspected, boils down to “Other races taught them”
Edit: This is a sarcastic remark.
Blizz gotta make sure there is a steady game for a steady amount of subscriptions to make their earnings.
The lore is second priority or third maybe 
Taught by the other races is the most likely way. Magecraft appears to be something you can learn rather than something innate, so it’s just about finding an orc who wants to learn and a tutor willing to teach them.
Mag’har mages are a slightly different breed in that they were taught by the ogres of the Gorian Empire in exchange for their lives. This means they are going to be Pretty Good At It.
They grabbed a book and read it.
There you go.
There’s a command that turns flavour text on again, if that helps. “/run ForceGossip = function() return true end”
Like Acrypha, other orcs could be more or less self taught. Altough knowledge from the other races most likely has sped up the process.
If I recall Chronicles said that Light and Void are the different sides of the same coin, then that could also be assumed from arcane and fel. If you remember the quest in Legion where you play as Illidan, he there lectures the eredar for wielding the fel clumsily and afterwards he shows what a master sorcerer could do with the fel. Illidan was able to quickly pick up fel magics for being a skilled sorcerer. So where human magi became warlocs then orc warlocks could learn the arcane using their knowledge of fel magics as a base.
Also a transition from shaman to mage is not too farfetched as Garrosh’s Horde was using dark shamans who forced elementals to do their bidding instead of traditional bargaining and honoring them. As arcane is virtually about forcing cosmic energies, then the practices of the dark shamans is really close to it.
I don’t really agree with this, to be honest. Considering the nature of Fel magic, it seems far more dificult to go from Fel to Arcane than the other way around.
We know for example that demon hunters can’t really use the Arcane actively anymore. Likewise, Demons seem to be incapable of using it, because it goes against their nature, probably.
While I won’t say whether or not it is impossible to go from Fel to Arcane, I doubt you can actually use your skills as a warlock to get good at Arcane magic.
Edit: as far as I know Dark Shamanism is practised through the Decay element, though I’m sure others know more about this.
He actually defeats all the demons with arcane (I think). Only later on he’d use fel magic.
This is more or less spot on - Arcane and Fel are aspects of law and chaos, respectively. It is nigh on impossible for a user of Fel magic to switch back to the Arcane.
Offhand, I can’t think of anyone who has switched back in lore. Usually people who give up using fel magic go cold turkey and don’t use any magic at all
I could see fel users going to void use. But I’m only saying that because of the satyr.
They can switch back to Shamanism, tho… I think Drek’thar did that, right? 
But yea, I can’t for the life of me seem to remeber anyone who switched from fel back to Arcane 
A fair few of the Old Horde warlocks went back to Shamanism I believe
Fel is told to be unfathomably addictive, I suspect that trying to use another form of “Arcane” magic would just be considered a gateway back to Fel.
There were Orc Mage NPCs in Vanilla. They just didn’t introduce the class as playable until later. Any race that can use Fel can use Arcane.
And Orcs are titan Off shoots anyway, it makes all the sense in the world that Arcane magic is in their blood.
Again, demons don’t seem to be able to do this. It’s more the other way around. Any race that can use Arcane could potentially use Fel magic.
Even Mr. “Arcane is impossible for me” Jace can still manage some arcane skills. It’s just more difficult. You also had the demons in black temple gorging themselves on the arcane shrine to “free themselves of their fel addiction”.
Original orc routes:
For mag har
I did mention the Demon hunters before. Yes, they can still do some arcane magic, but then they aren’t fully demons yet.
By the time we had the Black Temple, wasn’t Fel just a corrupted form of Arcane? Or is this in the Illidan novel?
This was from the Black Harvest questline in MoP.
I see. I’m not sure, what was the lore on Arcane <-> Fel back then?
It has changed a lot, at least we can hope that Chronicle keeps things canon. Unless they decided to make it even more non-canon than they are.