Assalamu Alaikum Brothers in Islam,
"Demolishing the Kaaba completely is much more preferred to Allah Almighty than shedding the blood of a Believing Muslim"
Is this hadith authentic?
On intentionally killing a believer
The qur'an teachs us:
But whoever kills a believer intentionally - his recompense is Hell, wherein he will abide eternally, and Allah has become angry with him and has cursed him and has prepared for him a great punishment. (4:93)
And do not kill the soul which Allah has forbidden, except by right. And whoever is killed unjustly - We have given his heir authority, but let him not exceed limits in [the matter of] taking life. Indeed, he has been supported [by the law]. (17:33)
and in the sunnah we find:
The Prophet (ﷺ) said, "Avoid the seven great destructive sins." They (the people!) asked, "O Allah's Apostle! What are they?" He said, "To join partners in worship with Allah; to practice sorcery; to kill the life which Allah has forbidden except for a just cause (according to Islamic law); to eat up usury (Riba), to eat up the property of an orphan; to give one's back to the enemy and fleeing from the battle-field at the time of fighting and to accuse chaste women who never even think of anything touching chastity and are good believers." (See for example in Sahih al-Bukhari)
"A faithful believer remains at liberty regarding his religion unless he kills somebody unlawfully." (See for example in Sahih al-Bukhari)
One of the evil deeds with bad consequence from which there is no escape for the one who is involved in it is to kill someone unlawfully. (See for example in Sahih al-Bukhari)
It is not permissible to take the life of a Muslim who bears testimony (to the fact that there is no god but Allah, and I am the Messenger of Allah, but in one of the three cases: the married adulterer, a life for life, and the deserter of his Din (Islam), abandoning the community. (See for example in Sahih Muslim)
From this perspective it is clear that killing or even being involved in the killing of a believing Muslim is among the worst acts a person could do. And Allah's punishment for this is very severe.
On ahadith the high rank of a Muslim soul/life
"Killing a believer is more grievous before Allah than the extinction of the whole world." (See for example in Sunan an-Nasa-i)
"The world ceases to exist is less significant to Allah than killing a Muslim man." (See for example in Jami' at-Tirmidhi)
“I saw the Messenger of Allah (ﷺ) circumambulating the Ka’bah and saying: ‘How good you are and how good your fragrance; how great you are and how great your sanctity. By the One in Whose Hand is the soul of Muhammad, the sanctity of the believer is greater before Allah than your sanctity, his blood and his wealth, and to think anything but good of him.’” (See for example in Sunan ibn Majah)
… "One day Ibn ‘Umar looked at the House- or – the Ka’bah and said: ‘What is it that is more honored than you, and whose honor is more sacred than yours! And the believer’s honor is more sacred to Allah than yours" (See in Jami' at-Tirmidhi)
The last two narrations see to em among the closest to your quote.
From the above narrations and the earlier references we can conclude that the meaning of the statement you quoted is correct.
As the soul or life of a Muslim is among the most precious things and therefore a building such as the Ka'aba can't never reach this high rank.
On the source and authenticity of this narration
لَهَدْمُ الْكَعْبَةِ حَجَرًا حَجَرًا أَهْوَنُ مِنْ قَتْلِ الْمُسْلِمِ
Here and in the following I'm translating from Arabic language. as these translations are of my own take them with the necessary care!
The stone by stone demolishing of the Ka'aba is easier to Allah than killing a Muslim.
and commented it by saying:
لم أقف عليه بهذا اللفظ ، ولكن في معناه ما عند الطبراني في الصغير عن أنس رفعه : من آذى مسلما بغير حق فكأنما هدم بيت اللَّه
I was not able to come across this statement with the given wording. But in its meaning in imam at-Tabarani's as-Saghir on the authority of Anas (ibn Malik) as a marfoo' narration: "Who ever harmed a Muslim unlawfully is equal to one who demolished the House (al--Ka'abah)
So even if the statement imam as-Skahawi quoted seems to come very close to your quote in both meaning and wording. There doesn't seem to be a narration that can be considered a hadith nor any authentic narration of the prophet () that would fit this wording.