Naming Dillema

[Almyrigan Hero]

You could still give them badass titles, but just make them more heroic.

Mag Ro'Nosh Dragonbreaker
Kozra Zan The Indomitable
Leyra Mong Mountain Conqueror
Gozor Ugnoz Ironskull
Roxor Wodan The Undefiled
Huzong Ror Crusher of <unique monster name>
Lazula Hodor <Lore villain>'s Downfall

 

[FifthView]

Last names aren't even really my issue, it's first names. How do you think of orc sounding first names?

This depends at least partly on the sort of sounds you want for orcs in your world. But you can do a Google search for "Orc Name Generator" and find some sites that will randomly generate names. Generate lots, and just pull out the ones you particularly like for your first names. Or at least the generators might give you some ideas.