We explore the use of femtosecond laser pulses to clean a variety of colors of spray paint from the Moruya granite, a stone with high heritage value that is widely used for monuments and sculptures in Sydney and New South Wales (Australia). The efficiency of the cleaning treatment and the effects on the stone substrate are evaluated using optical microscopy, optical profilometry, Raman spectroscopy, energy-dispersive X-ray spectroscopy, and colorimetry. We demonstrate that femtosecond laser cleans granite without damaging it and without discoloration when the laser fluence is set below the damage threshold of the stone.