This is my list of class combo additions for all races. I disagree with some of yours but I think my list explains why and you might find those reasons persuasive. (Or not! 
)
Alliance
Human
Druid: So all the Gilneans that were druids got turned into worgen? I doubt it. And Kul Tiran and worgens won’t teach regular humans to be druids? Doubt that too. Let’s be straight. Humans are a popular universal race. Like orcs. Give them as much as you can.
Nightelf
Paladin: They have been priests from day one. There are canonized NE paladins. The priests are adding to their lore with all the Elune stuff, adding paladins is a next logical step.
Gnome
None, they have great options that can be better balanced out with mechagnomes.
Draeni
Demon hunter: What happened to all the eradar draeni? Were there none that want to come back and use their demonic powers to redeem themselves? Keep in mind Velen’s son died BEFORE the device that reincarnated demons was destroyed. Perfect story line opportunity to bring him back in a way that isn’t so tragic.
Worgen
Paladin: Gil’neans were in the second war. Second war was fought with paladins in place of knights. Ergo worgen have paladins and always should have.
Monk: Suggest it be an Exile’s reach only option to fit with lore. This way all races can have monks which seems to be Blizzard’s intent.
Void elf
Paladin: If void elves can have holy priests, and lightforged draeni can have shadow priests, there is noting to say a void elf could not be a paladin.
Demon hunter: no brainier option. Anyone who would infuse themselves with fel wouldn’t bat an eye to do some void, and vice versa.
Lightforged draeni
Rogue: They have been fighting the burning legion for centuries. That they wouldn’t have developed a covert ops division is not justifiable.
Monk: No brainier. Should have been there already.
Dwarves
None. Excellent selection complemented with dark iron.
Dark iron Dwarves
None. They have almost all options anyway.
Kul tiran
Paladin: Same as worgen, significant participants of the second war. Actually more significant than Gil’neans. “Warcraft 2 Tides of Darkness” was literally named for their navy.
Mechagnome
Paladin: Clearly should be an option. When you’re upgrading yourself, why would a priest physically upgrade themselves and not try to become the fighter priests that paladins are canonically?
Shaman: A goblin was brought to mechagnomes as part of the alliance zone intro quest. That they would totally ignore how goblins have used tech to become shamans is kind of anti-cannonical.
Horde
Orc
Demon hunter: This one is actually great because it dips into the lore of the original non-night elf demon hunter: Grom Hellscream! Yes, he used his demonic enhanced strength to kill Mannoroth. As a bonus this adds 2 handers as a potential weapon that some have wanted.
Nightborne
Demon hunter: There are literally nightborne consuming fel as part of the storyline. Did they all just get fed to the animals in the zoo after the war was won? Or do they not reintegrate into nightborne society?
Druid: One of the bosses in Nighthold is a druid. Clearly they had them.
Undead
Paladin: There are holy undead priests. With Calia Menethil, there are holy undead. Paladins are the next logical step.
Demon hunter: If anyone hates demons more than the elves, and would do anything for revenge, even corrupt themselves with fel, it has to be the undead.
Highmountain tauren
While regular tauren have a good selection, the highmountain got the shaft with simply classic WoW options. This should be rectified.
Rogue: Logical option for a hunter themed race.
Demon hunter: Something needs to be done with the now fel infused blood totem.
Warlock: Same as above. Blood totem casters need to be reintegrated somehow.
Mage: Something different. But also with Dalaran and their new Horde allies in Suramar right next door, if they aren’t being trained as mages they are just negligent for not taking advantage of the opportunities that brings.
Tauren
Good how they are. Any new options should be given to highmountain to give variety and provide a tangible difference between the 2 races.
Mag’har orc
Paladin: How anyone thought an orc would be okay just being a cloth priest with a stick, and not a plate priest with an axe, is beyond me. Major oversight here.
Troll
They already have nearly every class option.
Zandalari troll
Same as troll. One having paladins while the other has warlocks is a great way to differentiate the 2.
Blood elf
Druid: Another obvious one. That the high elves were so in tune with nature, but insisted on no druidism because Stormrage was a butt to them, is kinda silly.
Vulpera
Good selection of classes already
Goblin
Monk: Another to uniquely add with Exiles reach to keep it in line with starting zone lore.
Neutral
Pandaren
Druid: I recalled a developer saying they wanted pandaren druids, but a bear that turns into a bear just didn’t make sense. Zandalari solved this issue with their unique druid forms. Pandas turning into turtles or maybe even an ox would solve this problem.