A man almost invincible to physical damage (regeneration from any damage in few seconds), with the power to kill people in few seconds from mid to short distance and being an exceptional swordsman, wants to become the king of the kingdom with the most powerful military force of his (medieval-like) world.
"Almost" because he has a weakness (that's the point of the story) that can turn him vulnerable to a quick death, however normal humans can't take advantage from this weakness, as only a specific group of humans have the power for such. Such group lives isolated and independent from the rest of the world and have no interest in killing him. That's the weakness for his invincibility, but he's still vulnerable to other ways of dying, like drowning, decapitation, etc. Basically, there's no "magic" in this world, only the casting of elements (fire, wind, etc.) by using a special type of energy (but these elements alone aren't enough for killing him), which this group can use.
So in order to become king, he plans on invading such kingdom and killing the current king. But he doesn't want to make noise and call attention, and just want to achieve his goal silently.
And here's the point of this question: What would be the obstacles for him to achieve his goal?
In case anyone wonders: that's just the story's beginning and most relevant info for this question.