So I'm gonna put out a story about a warrior who I want to be similar to legends. Like stories of fictional and real life legendary fighters like Neo, IP Man, Bruce Lee, Michael Jai White, Anime Fighters. I wanted to make a character's who's story feels like it came from oral tradition of an African warrior at the height of the Atlantic Slave Trade. The MC has some of the traits inspired by traditional ancient legends: heroic, tragic, silent, composed and I feel like it really works for him. And I want the feel of the story to be as archaic and barbaric as historical tales but I also want him to be somewhat a symbol of human exceptionalism. Which is what is bothering me though. In the story I'm struggling with what makes him truly exceptional. Throughout the tale he gets into large fights by himself and handles himself adeptly. But what makes him seem like a more awe inspiring legend: killing the warriors he fights or handling them without killing them? Here's an excerpt: It's giving me pause myself. I want Shuja to seem like a hero you can celebrate. But grisly murder doesn't seem befitting of a hero. This is literally the only person he has killed so far but I'm wondering would it seem much more heroic if he managed to defeat many dozens upon dozens of warriors without killing a single one? Or would a giant massacre elevate his true warrior status? What makes him more worthy of a legendary title?
The creation of a legendary paradigm requires two primary things that are then broken down into detail. Attributes that are sufficiently noteworthy of mythologizing A reason/drive for those who create a mythos around the person to do so. Why are The Beat Writers mythologized? Is their writing exceptional in a way that makes them utterly unlike that which came before or since? What was happening in the world around them to make that world latch on to them and create "The Beat Writers" out of them, a concept and idea much larger than the reality and a term they themselves never used? Why are Picasso and Dalí mythologized? What did they do to make them, the men, larger than life when there were other contemporary artists easily as renowned and important on the scene? This is what I would ask myself as regards your warrior. You've already answered the first part. His pwnage is awesome, uncontested. Now you need to ask yourself why The People would raise him to the level of legend. Why him? Why not others? What is happening in the lives of the people to make them need to fill this pedestal with his mythologized form? What makes him worthy will depend on that dynamic, and only you have that answer.
He could gain his legendary status from learning not to kill his opponents to win fights. The people he doesn't kill this time around would spread the word about how deadly he is, making others think twice about fighting him. Those brave or foolish enough to challenge him later in the story could end up in terrible pain, or simply humiliated, but I doubt the latter would fit the tone of your story. Ultimately, to become a legend, he would have to commit an act of incredible honour and bravery, gaining the respect of the people he protects, and the fear or respect of his enemies.
He sounds more like an anti-hero, which can be a good thing. Sometimes, characters who don't want to be acknowledged as heroes are the best ones.