There is a fundamental problem with your argument. And that is the unspoken assumption that beliefs directly evolve. A belief is not a basic capability like vision.
We can deal with he ideas of "sensing" and "longing for" a God seperately if it is relevant - for this post I will focus on belief.
What you really need to look at is the mechanisms of belief-formation which contribute to the belief and then see if THOSE have an evolutionary advantage. And you have to look at the full use of those mechanisms, not just their contribution to a single belief.
In fact it is quite easy to see how the general idea of Gods might have got started. Even today humans have an tendency to anthopomise natural forces (such as the weather) or complex machines. Even knowing it to be wrong we still attribute volition to inanimate objects if their behaviour is sufficiently unpredictable and especially if it appears capricious. We tend to anthropomprphise animals, too - even animals which completely lack even basic intelligence. Even with the "higher" animals it is likely that aspects of their mind are sufficiently alien that thinking in human terms is badly wrong.
And there is a good reason for this - it is a BIG advantage to be able to deal with other people in this way. A social animal must be able to successfully interact with others of its kind. Yet young children do have problems with this idea and some people sadly suffer mental handicaps which make them unable to get to grips with it.
So we have to learn to recognise "people" and to accept that they are thinking beings like ourselves. And in evolutionary terms all we need is a net benefit - the cost of false positives must be outweighed by the gain from true positives. Since this way of thinking - that so often leads to error - is still found even in modern humans who not only should but do know better we have good reason to believe that this is the case. The problems caused be error are far outweighed by the advantages.
So humans naturally tend to "see" intelligences which are not there - hopefully you can see that form there it is just a short step to a basic animism. From then on religion can complicate and develop through cultural transmission. And it is quite clear that modern beliefs in a God or Gods generally are produced by cultural transmission rather than any other means. And of course the capability to pass on what has been learned is another evolutionary advantage even if some of what is passed down is completely false.
™ Version 4.2