It is presumable that the Atreides, along with the rest of the ruling class, were agnostic adherents of the Orange Catholic Bible. You mentioned Appendix II in your question, and most of my answer draws from there.
Religion, like the other main forces in the Imperium, is also in a state of stagnation. The O.C. Bible was specifically made to defang religion in the wake of the Butlerian Jihad:
"We are here to remove a primary weapon from the hands of disputant
religions. That weapon -- the claim to possession of the one and only
revelation."
The Appendix lays out the dominant religious beliefs at the time of the Imperium. It doesn't rank them or even truly define what "dominant" means, but there's the O.C. Bible and then there's several "ancient teachings" found on specific planets. We must assume this means the O.C. Bible is followed everywhere besides those specific planets. The other two "religious beliefs" are the Bene Gesserit (who deny they are a religious order) and then the agnostic rulers:
The agnostic ruling class (including the Guild) for whom religion was
a kind of puppet show to amuse the populace and keep it docile, and
who believed essentially that all phenomena -- even religious
phenomena -- could be reduced to mechanical explanations
The Appendix goes on to later specifically state the opening of the O.C. Bible is an "obvious appeal to the agnostic rulers".
As a Great House, we have no reason to believe the Atreides were not followers of the O.C. Bible. In the Imperium, it's the default religion. Even if you don't buy it, you need to at least pretend to in order to rule.
As for Leto calling out Paul's flawed beliefs, that's a bit more complex. The series makes it clear that true religious belief is disruptive and powerful. The primary religion of the Imperium was designed to prevent more jihad. The Missionaria Protectiva infiltrated and maintained the pockets of non-O.C. religions, so the Bene Gesserit could use them when necessary.
Paul ends up using the Missionaria Protectiva to make himself messiah. As cited already in the answers, Paul tells the Reverend Mother about the Fremen saying, "God made Arrakis to train the faithful", and she grasps the horror of that statement - true believers finally unleashed into the universe.
But Paul is not a true believer himself. He knows he exploited their messianic beliefs, he does not want the jihad that follows, and ultimately ends up preaching heresy against his own religion. Leto is a true believer - he knows himself to be the messiah and commits himself to the terrible purpose.