Well I'm not sure whether it is possible to give a clear answer as AFAIK there is no historical backup. We can find an independent source (Claudius Ptolemy) from the 2nd Century B.C. mentioning a Place called Macoraba and a map from the 3rd Century B.C. which suggests that Macoraba was Mecca.
And as it was rebuilt many times it's hard to say which information circulated between the tribes of Qurraish!
Now the people from Qurraish should either
- because there still were some monotheists or people who still followed Abrhams/Ibrahims (peace be upon him) religion among them think it was Ibrahim and his son who built (rebuilt) it!
- or the Amalek عماليق were the builders (re-builders): the so called giants some tribes who lived in the arabic peninsula!
- or Qusay ibn Kilab (400-480 A.C.) قصي بن كلاب an ancestor of our Prophet Mohammed (peace be upon him) was the the builder (re-builder)
- or Jurhum جرهم -Banu Jurhum an originally yemenite tribe which has settled down there when the Well of Zamzam was found and Ismail (peace be upon him) later married a girl/woman from this tribe- could be known as builders/re-builders of the Kaaba!
- And maybe they knew about Adam and Seth the son of Adam شِيث (transliterated Sheeth in Arabic)
Don't forget that Qurraish themselves re-built it after the year of the elephant!
I'd like to add that this answer could back up that some of the Arabs might have known some of the earlier prophets (peace be upon them).
- The Kaaba was originally built by the Prophet Adam (peace be upon him) (it was also said that before Adam it was built by the Malaaika!) and later re-built by the Prophets Ibrahim and Ismail (peace be upon them) and i think it was rebuilt/repaired many times before and after that! In the Arabic Wikipedia Article you may find 12 "Builders/Rebuilders named"
- There have been many Kaaba's around the Arabic peninsula in pre-Islamical time as many tribes wanted to have a shrine like the one in Mekka, but somehow this special shrine was more attractive as a destination for those who wanted to make a pilgrimage!
And Allah knows best