The problem you pose exists in the real world. False religions clearly exist in our own world. As religions contradict each other, at most one religion is completely, literally true. All others must be false to at least some extent. Of course an atheist would say they are all false. Like at the most basic level, there may be one God, there may be many gods, there may be no god. Only one of these ideas can be true, so the other two must be false. Yet there are millions of people in the world who believe in each of these. So millions of people must be wrong.
So one can look at the real world and ask, Why do people believe in false religions?
If you want to know my perspective, I'm a Fundamentalist Christian. But I think a Muslim or a Hindu or an atheist could say much the same as what I say here.
From a strictly rational perspective, many of the questions are complicated and the evidence is difficult to evaluate. There are many scientific questions where intelligent, rational people disagree. Historians disagree. Mathematicians disagree. It's not at all surprising that intelligent, rational people disagree about religion.
Often, on religion and many other subjects, people believe what they want to believe. They don't examine the evidence and come to a conclusion. They come to a conclusion and then look for evidence to support it. Some things are pleasant to believe, so people choose to believe them regardless of evidence. What people find pleasant to believe varies, but so what? Like one person may want to believe there is a God because he finds the idea of a supreme being who is in control comforting. Another person may want to believe there is no God because he finds the idea of a supreme being to whom he is answerable disturbing.
Some people don't really think deeply about controversial questions at all. They believe something because that's what their parents told them or their teachers told them or they saw on TV. I recall when I was in school my physics teacher once said that he often asked his students if they believed the world was round. All of them had always said yes, of course, believing in a flat Earth is silly and ignorant and unscientific. So he'd say great -- How do you know the world is round? How could you prove it? Few could give any scientific or logical argument. They knew the world was round because that's what they were told. They had no idea how to prove it. If most people couldn't give you evidence for something as simple as why the world is round, how many could truly explain why they believe what they believe about complex questions? I've often mused that, I like to think that I'm a scientifically minded person, and so I could tell you what experiments have been done to prove that the world is round or that special relativity is true or etc. But in the vast majority of cases, I've never done the experiment myself. I just blindly believe the textbooks that say that someone else did it and got these results.
Atheists often say, You religious people just believe this because that's what your parents or your pastor told you. And I readily concede, in some cases true. But by the same token one could say, You atheists just believe this because that's what your professor in college told you or you saw on that documentary on TV. And if you are honest you must confess that for many atheists, that's true.
So all that said, you could justify why your creatures believe in this religion by ...
Giving some reason why it is pleasant or comforting or otherwise satisfying to believe it. Why would someone WANT to believe it?
Giving some sort of evidence, however slim, that it is true. Maybe easily rebuttable by a skeptic, but things that a believer could say, Look, we have concrete evidence that this god really lived 1000 years ago. Or, there are many who claimed to have witnessed this appearance of the god.
Have authorities who preach the religion, schools teach it to children, parents teach it, etc, so that it is easy for those who don't think too much for themselves to just believe it.