At the very start of the game, Kaim and Seth are caught up in the meteor that crashes down over the battlefield. Given the fact there are no bodies around when Kaim comes to, it's pretty obvious that they themselves were reduced to nothing but ashes at some point. Since they're 'immortal' it's fine that they come back, but the real issue is.. how do their clothes survive? Kaim sort of gets a pass because he's wearing armour, and you can see helmets and pieces of metal that still survived on the ground, but Seth's outfit? Not a chance.
A better question regarding that scene would be: Why does the threat of being frozen in ice or trapped in a cave scare the immortals, but not the threat of being buried alive / sealed inside drying lava? A giant meteor falling from the sky could potentially do either of those things to Kaim, so he should be more terrified of it than the soldiers fleeing around him.