All religions start small. You basically start with a cult and once you get adopted by a large enough power you become a religion.

So the first signs would be an AI led cult.

Imagine, if you truly believe you are interacting with an entity with superhuman intelligence, you might take its word as gospel as you believe that "it has all the answers".

Admittedly this is a little far-fetched, but you only need a few people (12 or so) to get started...