An immortal who travels space trying to find the aliens who made him immortal

Question

I am trying to find out about a series I read when I was younger. It was about either a cave man or ancient native American who was turned immortal by aliens. He travels across space trying to find the aliens that "fixed him".

I seem to remember that he was a shaman ready to die when the aliens accidently hurt him while landing their ship and they decided to fix him. I keep thinking the characters name is casey, or KC for some reason.

I also remember in the short story that he can regenerate mass to replace damaged or missing body parts by eating.

Answer 1

Possibly In the Face of My Enemy by Joseph Delaney? Per the summary provided by beichst (whom you can thank for the find) in response to another more recent question:

Eighteen thousand years ago a priest ascended a high place, there to hold converse with his gods. That night the gods chose to bless him with their physical reality. Alas, mortal flesh cannot bear the presence of godhead, and so he died. And was reborn. But ever after he was not as other men. He could change his form at will, his wounds healed instantly. . . and he did not age. As millennia passed he grew very wise, and came at last to understand. His destiny lay not among men, but among the stars.