Look I have no idea what the "plot" or gameplay of Stellaris might be like, but I don't get the fascination for wanting religion in the game. Religion is just a subclass of ideologies. Differing ideologies may cause division within a species, and possibly lead to issues around morale, corruption, cohesion, happiness, etc within a species able to love/understand/hate those ideologies.
However it is extremely unlikely that a truly alien species will have thought patterns remotely able to understand the ideologies of another species, let alone their religion, or even be able to communicate with them, or even be able to perceive their existence.
Why bother to add religion when there is already so much you could be working with.
Probably not in the game, but what would a 700m long methane breathing gas bag looking to colonise gas-giants have in common with a oxygen breathing primate that prefers tellurite planets? Maybe they go to war because our cloud scoops keep accidentally sucking up their young? Or our hyperspace lanes mess up their beautiful sub-space curving art works? Or our warp-drives hurt what passes for their ears? What about a hive-minded virus analogue with a penchant for oceanic planets? Would it even recognise multi-cellular organisms as sentient? or just as hosts? Would a silicon based crystalline life-form even be able to communicate with a carbon-based pelagic life-form?
Lets just say it is enough that they are alien, ugly, and all their bases are belong to us.