This is a great question, as in the fact that trying to trace these bibical origins are hard. First, let us look at the Acts 17: 22-27:
22 Then Paul stood before the meeting of the Areopagus and said, "People of Athens, I can see you are very religious in all things. 23 As I was going through your city, I saw the objects you worship. I found an altar that had these words written on it: TO A GOD WHO IS NOT KNOWN. You worship a god that you don't know, and this is the God I am telling you about! 24 The God who made the whole world and everything in it is the Lord of the land and the sky. He does not live in temples built by human hands. 25 This God is the One who gives life, breath, and everything else to people. He does not need any help from them; he has everything he needs. 26 God began by making one person, and from him came all the different people who live everywhere in the world. God decided exactly when and where they must live. 27 God wanted them to look for him and perhaps search all around for him and find him, though he is not far from any of us.
As you can see, when God created humans, he wanted them to look around for him and search for him. This is one of God's plans, and in doing so, he created this "hole" that cannot be filled by any other: in short, that "God-shaped hole" was created by God for us to look for him.
I have another verse as example; let us look at Ecclesiastes 3:10-12:
10 I have seen the burden God has laid on the human race. 11 He has made everything beautiful in its time. He has also set eternity in the human heart; yet no one can fathom what God has done from beginning to end. 12 I know that there is nothing better for people than to be happy and to do good while they live.