There might be issues with religion even before theology formally sets in.
I think I can confidently predict that D&D, with its sloppy world-building, probably got it wrong when it had full pantheons of gods for every intelligent species. With overlapping spheres. While humans had several full pantheons of gods, also with overlapping spheres. . . . And Warhammer 40K's weakness in theology also hits here. If you don't even know how the Emperor, who unquestionably was born many millennia into the existence of the universe, can somehow create humanity, the question of how aliens, which the Emperor hates, or is supposed to, can exist. But before it's theologically depicted, you can have a welter of confusing and contradictory myths explained and counter-explaining every intelligent species.
Theologians would start to systematize. Augustine was the first to do so, I believe, discussing the possibility of fauns and other such creatures. He pointed out that quite monstrous human births did occur, and perhaps therefore entire monstrous races could exist while still being of human origin. Of course, this raises little questions about the origins of all these species -- the contradictory myths would be rather crucial here. Then, Beowulf classified elves as of human descent: to be more particular, along with Grendel and other monsters, the ylfe were descendants of Cain and enemies of man.
Not settling the question can work well, particularly if the gods stay off-stage and provide no unambiguous hints (since they would be in the know). The medieval chivalric romances managed to swallow up the Good Folk, without settling anything exactly about origins. To be sure, later romances tend to rationalize them into enchantresses. (Only enchantresses. And the one who raised Lancelot du Lac did not live in a lake, she only had the illusion of a lake over her home. . . . ) Sir Orfeo used the stuff about people being apparently dead and then slipped into saying the Land of Faerie holds the actual dead, which was one theory.
The others were that they were another rational race, that they were a demoted kind of angel, and that they were full blown devils. To be sure, choosing one has its consequences, but not all such consequences are bad. L. Jagi Lamplighter's Prospero's Daughter does wonders with the demoted angel bit.