Sandor (43, 15), who lives at the Desolated Wilds, can promote you to Warmonger if you enter Pao-Kai Nest and defeat the monster there. In addition you need a blessing of Dragon god of air from the quest "Forge of Heroes".
Move to the Crag (1), because from there you'll have the fastest way to your target. Use the portal (2) east from the gate to teleport into mountains. Now keep going forwards until you find a cave (3).
This is one of most difficult caves, because inside you'll encounter only elite opponents. It would be best to have Fire Blast spell to make your fights easier.
There are no gates inside (4) so start fighting your way through to the entrance to the second level (5).
On the next level (6) you have to talk to Blind Shaman (7) but other Orcs block you an access to him - kill them all. Once you talk to him, the gate to Pao-Kai will open (8). During the fight use regeneration and fire spells, because they are good against him.