So in terms of the classes many have a particularly unique cultural value, significance or overall backstory to how they connected to their respective race.
This thread is to either provide justification or explanation towards how each race bellow fits into the Paladin order / vice versa. 
Night Elves
Lets all for a moment ignore the ‘Delas Moonfang’ ordeal who became a basic paladin in Legion via the mundane human tropes & speak more on the level of something centrically more Night Elf themed …
- As we know, originally in Night Elf lore – Their priests & divine order tend to follow the order of Elune. You could probably have a Night elf priest attempting to teach their ways to another only to find the divinity they attempt to channel to be more held within, and yet erratic.
- Later you could have it that the priests, sentinels and others amongst their culture could see an opportunity in these individuals & attempt to establish this lot into an order “The Knights of Elune” — Those who use their unique nature with Elune’s light to harness the power in a way unseen amongst their people before. This order will be dedicated to protecting their people, preserving their future and upholding their ideals.
Pandaren
At Krasarang Wilds in Pandaria — from the Horde questline, you encounter the Pandaren ‘Kang Bramblestaff’ who was impressed by the Sunwalkers’ fighting style and intended to learn from them. 
- So it’d be cool for Kang Bramblestaff to make a reprisal return as a Pandaren Sunwalker, who learned the way of the Sunwalkers & taught those ideals, techniques and ways of wisdom to Pandaren all around (Horde & Alliance alike).
- Given the Pandaren lore, you could potentially combine & extend it with the August Celestials too – Having their monks & priests of their respective temples teach the new order of Paladins various virtues and ways towards tapping into divine power.
If not Kang, then perhaps a handful of Pandaren whom Kang had taught what little he learned to others at a few temples — Who all then refined it with their sacred teachings, mingled with other temples & shared their teachings with one another and ultimately birthed a new order amongst their peoples.
Gnomes & Mechagnomes
Now I know what you’re thinking (for some of you at least) – “Gnomes!? But they’re … Well, gnomes?!” — but alas you also forget that the gnomes already have priests, so Paladins aren’t too much of a far step from such.
- That aside I feel a good lore connection to their paladin order would be — Order itself …
The Titan-kind of order.
- After all — We see a handful of Titanforged using abilities that looks like light, but is harnessed from order.
Thus you could potentially utilise the gnomes wit & ingenuity from gleaning over Titan technology gathered from Titanforged Facilities all around Azeroth from over the years — and having learned how to harness some powers & magics of order towards the ends of using the light cleverly in a whole new cluster of unique ways!
Trolls! 
I feel like the trolls should pull a page from the Zandalari trolls original design for paladins, as prelates of the loa! 
- Zandalari paladins later however had their lore changed into “Oh no we get power just from Rezan’s teachings, not so much the loa” – which I felt was kinda lame & sort of homogenized them with the other typical paladins.
Lets not do that
It’d be cool for trolls to get more oomph in troll lore (especially the loa) and have an order amongst them that tap heavily into various powers of the collective loa themselves 
Orcs
For Orcs, I thought utilising their connection to the elements would be a good way to go. How do I mean some may ask?
- Within Chronicles Volume 1 – It states:
“The cataclysmic birth of the cosmos also flung shards of LIGHT throughout reality. These shards suffused the matter of myriad worlds with the spark of life, giving rise to creatures of wondrous and terrible diversity. The most common forms of life to appear were elemental spirits — primordial beings of fire, water, earth and air.”
You could state that the elemental spirits hold various small degrees of light coursing through their beings at their core — Then perhaps have the elements reach out to those who hold a poor connection to the elements themselves, yet still hold a reverence for their spirits and see a new potential within them … The ability to utilise other various powers.
It could be depicted that the elemental spirits knew that although these individuals did not hold an affinity for the elements themselves, they knew the light they shared could be harnessed uniquely — Thus pooled their power together to gift those they considered worthy. And from these gifts of the elemental spirits, birth a new order of paladins.
Void Elves! 
Now then 
There’s been a LOT of discussion with void elves + paladins, so here I go …
- Recently in the new Dark Heart questline, they had a Void Elf “Knight of the Eclipse” who was a sort of Paladin using concencrate, so I’d argue they’re in the making with their own unique lore to help justify it — Probably to the degree that it’s not a complete affront to the lore.
However, for these “Knights of the Eclipse” if they added void-visuals to all their spells & gave them unique spell-visuals to emphasise the void-aspect, and created some ‘Void-Knight’ lore — That’d be sick! 
Personally I’d love if we could encounter a void-god (Void-Naaru) — Who is said to be far more powerful than L’ura (the void-naaru that Alleria consumed).
This unique Void Naaru being one who surprisingly wants to live in harmony with the cosmos other than others of their kind who seek to simply corrupt, consume and dominate it … After such we could use them as a benevolant & wise naaru, but one of such who is situated with the void than the light – and teaches their ways to their respective followers and ‘Knights of the Void’.
Mag’har Orcs
Honestly if they do the void-god idea as per above 
I feel it could probably be a fitting match to do “two birds with one stone” there 
Have the Shadowmoon Clans revere the void-god & perhaps tell stories of a prophecy from their days of old (You could potentially do this for both variants of orcs)
- Having an order of Void Knight orcs – especially those who follow a Void Naaru, would be fitting for the alternate universe orcs too, given their gripe with the light
However alternate universe orcs aside, it’d be good all round – Something new & refreshing. 
Worgen
For Worgen, I feel focussing more on their Gilnean culture than their wolf nature would be appropriate. Given they have their own cathedral & all, it’d be fitting for them to be inspired from their other human & Draenei allies and ultimately form their own unique order of Paladins.
You could have all sorts of new cathedral armour that have unique patterns to that you see on their stained glass and after such also combine it with unique claw features (as a reference to their people who are worgen). Personally I think making such gear merely available to ALL Alliance & not just worgen would be fitting, as it would allow some to roleplay their humans as Gilnean, yet not transformed to Worgen.
Nightborne
For the Nightborne, I feel you could do one of two ideas.
- Embracing the order of Elune once more – Afterall the tomb of Sargeras has been cleansed of demons, and was once the grand Temple of Elune (and is like … right there) then giving them a similar deal to what’s presented to the Night Elves (perhaps having them form a treaty for negotiations? Temple visitation rights ← for → Elune teachings restoration & shared knowledge).
or
- Having their shared connection with the Sin’dorei for assistance to form their own order of Paladins, separate from the Nightelves yet potentially dedicated to the Elune and forming their own unique order + culture from it.
Needless to say, I’d wager that the second would probably be more popular.
And more …
That’s all I’ve got for now, as I don’t want to make the thread creation-text too long.
- Enjoy!
… However, feel free to post your thoughts on the thread upon how to extend bellow, perhaps ideas you have for the other races and your own unique ideas to add onto what’s been presented above! 
Honestly it presents a unique opportunity to fleshen out & extend their lore more within Azeroth — So it’s not just human potential hogging up ‘shining moments’ in every class category, but give orcs some wiggle room to have some more of their own too.
Such as:
