Карандаш is a loanword originally from Turkish, as far as I know. In Turkish kara daş means 'graphite' or 'pencil', but literally 'black stone'.
No, the noun is in the nominative, it's "Where is my pencil?", not "Where is my pencil's?".
There is a French company by the name of Caran d"Ache producing high-class coloured pencils.
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.
I always confuse pen and pencil. Pen = pen, pencil = potlood. One of these days, I'll manage.
карандаш 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.