There is a hadith with a grade of hassan (good) that stipulates that the black stone descended from Paradise. The hadith was documented in Jāmi' at-Tirmidhi, Hadith 877 and Sunan an-Nasā'i, Hadith 2935:
عَنِ ابْنِ عَبَّاسٍ، أَنَّ النَّبِيَّ صلى الله عليه وسلم قَالَ:الْحَجَرُ الأَسْوَدُ مِنَ الْجَنَّةِ
It was narrated from Ibn Abbas that the Prophet said: "The Black Stone is from Paradise."
For a matter not related to law or rulings, a hassan hadith can be used as proof.
Apart from the hadith by Ibn 'Abbās on the origin of the black stone, other stories are not corroborated: Gabriel bringing the black stone from a nearby mountain, or that the black stone wasbeing given to Adam to erase his sins.