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.