This post is inspired by the SSC Book Review: The Secret of Our Success. To (double- or triple-)quote the relevant parts:

the best hunting strategy requires randomizing

and

If you’re generally predictable – and Scott Aaronson says you are – then outsourcing your decision to weird birds might be the best way to go.

This is a somewhat general pattern: to deal with smart adversaries effectively, randomization is, on average, the best strategy. Matching pennies and Rock/paper/scissors are some classic examples. Also, humans (and probably animals in general) are apparently poor randomizers. I assume because a built-in biological random number generator of adequate quality is expensive. I don't know if this is a good assumption. A quick online search does not refute or confirm this, and randomness is everywhere at the cellular level, but maybe not at the level of the single organisms.

Fortunately, true randomness is everywhere outside in the physical processes, and is cheap to access, and the augury and divination mentioned in the reviewed book are good examples of that. So, relying on external randomness might be an evolutionary adaptation that improves survival. (Is this so? Then we would see similar behavior in other animals' strategies for dealing with adversity, be it hunting, gathering or something else. Do we?)

Of course, the next step, consciously understanding what randomness is and why it is useful, is borderline impossible for any animal but a rather advanced human, and even then it's iffy: even statisticians are not immune to behavioral rituals. And given our awesome powers of rationalization, we justify the randomization rituals as predictive, not just useful.

And so we have a Goodhart-like situation, where a proxy becomes the goal, and is no longer a useful proxy:

The "true" goal is to improve the odds of finding or cultivating a resource necessary for survival.
The chosen proxy is to rely on an external randomizer.
The internal justification for it is that it has larger predictive powers then the person's logic or intuition.
Thus believing in an external power that is larger than oneself has evolutionary advantages and can stick, so the proxy becomes the goal, even though it gives little or no advantage in most situations that do not require randomization.
Ergo, "a God-shaped hole" in one's heart.

The above is largely a speculation and is missing a fair bit in order to become a quality model of how the need to believe in the supernatural may have been selected as an evolutionary advantage. But I don't see anything immediately wrong with it. It also immediately makes a number of predictions, such as some non-human animals using external random events to guide their behavior, instead of basing it on more deterministic factors, or on an internal generator of randomness.

It is worth noting that this might not truly be a Goodhart-like situation, since the proxy is still useful in its original context, and, potentially, in other contexts, such as community building.

I have not put any research into whether this has been discussed before, here or elsewhere, my apologies if this is a repetition of something already well known.