The challenge of orc paladins, to me, is that it’s an inherent contradiction; orcs and by extension most of the Horde are a capital-C Chaotic society where might essentially makes right, whereas paladins are almost always depicted as being champions of Law. I think there’s a way to do it by leaning into the sacrificial aspects of being a paladin, though.
The paladin fantasy, for a really long time, involved a pretty clear vein of self-sacrifice; there was stuff like Hand of Sacrifice, which literally had it in the name, Divine Intervention which straight-up killed you so you could save someone else, and examples in lore from Tirion to Maraad to Bolvar and back. I think it would be way more interesting if orc paladins leaned into that theme, as opposed to being more on the Deus Vult side of things.
We know orcs value self-sacrifice, since they venerate people like Grom, for whom they feel he giving his life to fix his mistake no only redeemed him but made him a hero. Orc initiates could be mostly rejects and-or those with nothing left to lose - criminals, washed-out peons, veterans of the Old Horde haunted by their past, and the like. Giving up something major would be a requirement of joining - something like “my place in society,” forcing themselves to become a nomadic knight-errant; “my identity,” to become a helmed, anonymous crusader, such that no one will know of or mourn their death when it comes, or even body parts, in the Shattered Hand tradition.
Orc paladins would “learn” to use the Light from humans and draenei, but only in the loosest sense; given that they’re factional enemies, orcs wouldn’t so much learn their traditions as co-opt them from second-hand experience in neutral organizations like the Argent Dawn. That way, the tradition of orc paladins isn’t dependant on another race to exist, and they’re allowed to keep only the things that are valuable to them and change the rest, as opposed to being Blood Knights 2.0 or Vindicators 2.0 or whatever.
This also allows orc paladins to avoid the Earthen Ring Problem, where everyone basically gets along with zero mention of tensions along racial or philosophical lines, despite large chunks of the rest of the game being about that. Horde paladins could be chuffed that orcs didn’t learn from their traditions despite being allies - with the orcs countering that Blood Knights are ultimately selfish, and Sunwalkers are basically just advanced druids anyway - and Alliance paladins could find it anywhere from offputting to downright insulting that their largest hereditary enemies essentially stole and twisted their religious teachings without permission.
This would all combine to paint a picture of a group who’s liked by basically nobody and is not exactly sunshine-and-rainbows to be a part of, but who are free to do the right thing because it’s the right thing, as opposed to doing it for tactics or Honor™ or any external factors.
I’ll leave their level of self-awareness about the Horde’s past to the reader’s taste.