What would a Human Warrior offer in combat/power that a Human Paladin wouldn't?

Paladins are glorified battle priests. They rely a lot on the light magic to fight - wich is cool and useful, but the warrior is kind of an underdog. No special magic, just your sword and your wits. If a warrior reaches the elite status, you can bet that he’s more experienced than most elite paladins, since if he’s not an elite he’s probably dead. If you mess up in battle, the light won’t heal you, you just bleed to death.
Being an underdog also favors other specialities like tactical thinking and strategy, since in order to stay alive you need to constantly look for and exploit weak points, naturally making the warrior more inclined to battlefield tactics and leadership in big army fights. It’s less about individual power and more strategy, experience and brute strength.

Well, Turalyon, a recent trained paladin, defeated Orgrim Doomhammer, one of the greatest heroes of the horde…

To be fair, Doomhammer just had the fight of his life against Lothar, not sure he was at his best when taking on a new challenger. Turalyon was also having a life defining moment there when he finally accepted his role. Just saying if there was a rematch, outcome may have been different.

Edited:Grammar correction. Defining, not denying

Yeah, he could barely stand after.

A gasp escaped Turalyon as pieces of the legendary sword fell to the ground. And Doomhammer‘s blow, now unimpeded, continued its glittering downward arc, striking the top of Lothar‘s helm with a sickening crunch. The Lion of Azeroth swayed, bringing his ruined sword down reflexively, and laid open Doomhammer‘s chest with the jagged half-blade before collapsing himself. There was utter silence as both sides stopped fighting and stared at the Alliance commander splayed upon the ground, his body twitching as the life fled him. And then nothing moved save the pool of blood spreading rapidly from beneath his ruined head.
Doomhammer took an unsteady step, one hand rising to press against the gaping wound across his torso. Blood leaked out around his fingers, but still he stood straight and, with an effort, raised his hammer high above his head.
"I have conquered!‖ he proclaimed in a hoarse whisper, swaying and spitting blood but still victorious. ―And so shall all our foes die, until your world belongs to us!

Doomhammer destroyed Blackhand, the shadow council and had Guldan as his servant, even after a hard fight Turalyon was too young and unexperienced to even have a chance against him, warrior vs warrior he would have been another casualty just like Thrall vs Garrosh, the only way a light or magic user could lose is by fear, Grom Hellscream could possibly have better chances against such enemies

Who had in turn just defeated the greatest hero of the Alliance, so Lothar might have softened him up a bit.

I’m pretty sure Warriors are using at least some small amounts of magic. Your own magical weapons and armor aside, when was the last time someone could injure someone and slow them down by pretending to roar like a dragon? Thunder Clap and Storm Bolt also come to mind. And I wouldn’t be surprised if Bloodthirst and Victory Rush were a basic form of Blood Magic.