Both the company name and the word for pencil are taken from Turkish (or maybe some other Turkic language) "kara taş", which means 'black stone'. I think it came from Turkic into Russian, and then was borrowed for the French company name.
карандаш sounds like Turkic "qarindash" (kardeş in Turkish), which means brother haha. Though it does not mean that, it is borrowed from Turkish/Tatarsky the phrase "kara taş" which means "black stone." literally.