For Win8, there is not product key sticker on the bottom of the laptop. The product key is burned into the bios, so all you need to do is install Windows 8 that came with the laptop and it will automatically activate. There should be a recovery partition, have you tried that? Look at the laptop manual to see what keys you should press to access it.
My new laptops came with no COA's either, and no install CD. You are suposed to make a CD set yourself, but it is to late for you now if you deleted the restore partition. I usesed magic jellybean to get my keys and saved them in notepad for future reference.