I didn't read the first part, so I may be off on a few things. But to me this story seems like it wants to be Conan. Now I love Conan stories. I think they're fantastic. Robert Howard was awesome. But there is a vast difference between conan and this piece.
The reason I assume it wants to be Conan is two fold. The first is the short "chapters," and the fact that this story is marked as "part 2" rather then "chapter 2." If you were going for a full novel, the quick breaks would seem pointless. as they are, they detract terribly from what's going on. Each break marks a new climatic ark, and because they're so short, that climatic arc never really gets very big, or goes anywhere, or however you want to say it. In short, the fewer you have, the better you'll be. Conan, while essentially long short stories (is that even a real way of saying it?) used breaks like you have here, but they were spaced greatly.
The second reason I assume it wants to be Conan is the feel of the piece. The plot doesn't seem very large, with a singular goal and a very powerful principle character. He's a bit more straight forward then Conan, but that's not bad. Conan was a rogue and a barbarian. This is a military Captain. I would expect a difference. Because the small plot (and by small I mean simple, not Wheel of Time Complex), I would expect more character and setting. Since they're going from tent to city, I was expecting more immersion in that change. But we didn't get it.
In Conan, we are immediately given a near perfect vision of how the setting appears (most notably in "The Servants of Bit'yachime or however you spell it). Much of Conan is very visual. We have no questions as to what the place looks like, and how Conan interacts with it. In this story I often find myself curious as to the lay of things, learning they are there or what they are only when or after things occur.
The fighting is . . . okay. It's very tough guy stuff and that's a great way to give us character. yay. However, hitting someone's face with the back of your head, hurts you more then them. The back of your head is the weakest part of the head. Hitting someone with the back of your skull will most likely drop you, even if you hit them in the nose. That part of the skull, after all, is quite strong even if the nose is flimsy.
And since their in a city, I'm surprised our hero hasn't grabbed . . . I don't know . . .a table leg, or a chair leg, or a sharpened rock, to hit things with. I'm sure most of the tech level of the piece was described in the first part so I'm not sure as to what would actually be available. Then again, giving us more setting would help with that.