I suspect they're more linked with our ancestral hunter-gatherer traits. It seems logical that early humans would go periods of time without eating while hunting, then consume a large amount of protein and fat in a short period of time.
Religious and cultural fasting, however, would likely have not occurred until the development of language which is estimated at 20k-50k years ago. That's not a particularly long time on an evolutionary scale.