This was an English language short story/novella I read around 2000-2010. I believe it was in some anthology, but possibly it was in a SF/fantasy magazine like F&SF that I read it. It may well have been from several decades prior to that.
There were various fantasy elements, but it has a somewhat SF-ish premise.
In ancient times (something like several-thousand B.C.) cults of numerous gods have recently started springing up. These are gods that can physically manifest in various forms. I think they either drew power from worship (I looked in the TVTropes page for that trope but didn't recognize a mention of this story), or just enjoyed sadistically playing with weaker species. It somehow is learned that these gods are not native to Earth but are psionic invaders from other stars, that can incorporeally travel to other star systems and even take physical form (or apparent physical form) if they infect minds with belief.
The main protagonist is some wanderer (warrior type, maybe?) who somehow acquires a fellow traveler -- I think that as he's traveling early in the story, he may have come across and rescued her from some controlling (literal) witch. I think the girl may have had some sort of age-accelerating spell imposed on her before he rescued her.
I think one or both of them are captured by some god at some point late in the story, but they somehow manage to escape. (I think that god may have been minotaur-like in form, but I don't recall if he had a labyrinth of some sort.)
They somehow acquire some sort of object that presents a threat to the gods, but they are unable to use it themselves (nor, I guess, find anyone in the world at the time who can use it). They want to hide it so that someone in a later age can use it, but face the problem that since the alien gods arrived, no secret can be kept forever, because when any remaining unconverted person dies, their soul comes under the power of the gods, so all is eventually known to the beings.
At the end of the story, while traveling in search of a way to hide the object, the pair are shocked to discover that the object missing and realize it must have accidentally fallen out of their bags while they were crossing a wide, trackless desert. They realize this was in fact the best possible outcome, and hope it's found in some later age.
An answer to this pertinent question mentions that A.E. Van Vogt played with the "gods feeding on human worship" idea in several of his stories, but the specific story described in the answer and the teaser text on the cover pictured there don't match the story I'm looking for. (In my sought story, the protagonists were mortal and all gods were evil manipulators.)