I don't think that humans have an innate sense of God and the afterlife per se, I believe it is a natural response to having a brain that is capable of abstract thought, complex, conflicting emotions and animal impulses, coupled with being placed in an environment that is extremely complex and full of wonders.
Humans will always try and find explanations and 'reasons' that the world is the way it is and where it, and we, came from, many modern scientists spend their lives doing just that and, as theories go, the God theory is tricky to disprove even today let alone 10'000+ years ago. As for the afterlife, death is such an important event that it is no surprise that superstition and ritual will surround it, and the belief in an afterlife helps to ease the pain felt by the living when faced with their own or a loved ones death. It is living in groups and group efforts that have helps humans evolve into what we are today and with living in groups comes social order and ceremony, it is not surprising that the primitive beliefs crystalise into religion the world over.
So, was there an evolutionary advantage to shared group beliefs about the nature of existance? Probably, the theory fit, it didn't increase our chances of being eaten by a sabre toothed tiger, made us feel better and helped us all to get along. Then, cilvisitation marched on, and we are where we are today, a belief in God or the afterlife won't kill you, can make you friends, feel wanted and secure but it doesn't mean in is correct.
/// So the whole history of rational inquiry about the nature of existance has a background of being wrong at a rather fundamental level. /// Yep, and God is one of the wrong ones.