Pretty sure this is House of Bones by Robert Silverberg. It is a short story, first published in the 1988 anthology book, Terry's Universe.
This review of the anthology book, Dangerous Dimensions, offers an overview of the plot, noting that the protagonist winds ups stuck 20,000 years in the past, where he's taken in by a tribe, but also asked to kill a lone man wandering the outskirts of the tribe's territory.
Gebravar in "House of Bones" travels back 20,000 years in time to visit our ancestors. It was meant to be a two-week excursion, but it appears that he's stuck in this era. Luckily, a tribe grafts him in, and he has a home with some safety. However, the tribe sends him out to kill a "ghost," a tribe-less man who is wandering on the outskirts of the tribe. Gebravar isn't sure if he can do it.
Reading through the story itself, the protagonist was sent back in time from the year 2013 by a mechanism called the Zeller Effect rainbow.
I was supposed to be here just four days and then the Zeller Effect rainbow would come for me and carry me home. Of course within a few weeks I realized that something had gone wonky at the uptime end, that the experiment had malfunctioned and that I probably wasn't ever going to get home. There was that risk all along. Well, here I am, here I stay. First came stinging pain and anger and I suppose grief when the truth finally caught up with me. Now there's just a dull ache that won't go away.
It also transpires that the "ghost" or "Scavenger" he's asked to kill is actually a neanderthal.
In early afternoon I stumble across the Scavenger Man. It's pure dumb luck. The trail has long since given out -- the forest floor is covered with soft pine duff here, and I'm not enough of a hunter to distinguish one spoor from another in that -- and I'm simply moving aimlessly when I see some broken branches, and then I get a whiff of burning wood, and I follow that scent twenty or thirty yards over a low rise and there he is, hunkered down by a hastily thrown-together little hearth roasting a couple of ptarmigans on a green spit. A scavenger he may be, but he's a better man than I am when it comes to skulling ptarmigans.
He's really ugly. Jeanne wasn't exaggerating at all.
His head is huge and juts back a long way. His mouth is like a muzzle and his chin is hardly there at all and his forehead slopes down to huge brow-ridges like an ape's. His hair is like straw, and it's all over him, though he isn't really shaggy, no hairier than a lot of men I've known. His eyes are gray, yes, and small, deep-set. He's built low and thick, like an Olympic weightlifter. He's wearing a strip of fur around his middle and nothing else. He's an honest-to-God Neanderthal, straight out of the textbooks, and when I see him a chill runs down my spine as though up till this minute I had never really believed that I had traveled 20,000 years in time and now, holy shit, the whole concept has finally become real to me.
In the end...
... the protagonist realises he can't go through with killing the neanderthal, and returns to the tribe with the neanderthal in tow. He anticipates that the tribe may decide to kill both him and the neanderthal, and he's willing to fight them to the death if it comes to that. It turns out however that the tribe members are pleased to see that he didn't kill the neanderthal. He concludes that the whole thing was a test to see how civilised he actually was.