We have 2 Bolts and a Volt; and had lost the Volt fob at one point. After numerous unsuccessful programming attempts with used ebay fob, I ended up purchasing a virgin fob & metallic key here:
https://www.gmpartsstore.com/oem-parts/ ... r-13529664
(search for your particular vehicle)
and it programmed per manual instruction. I would imagine the same thing for the Bolt, as the manual instructions are very similar. I did have to go to the dealer to have the mechanical key cut but it was weird that the labor cost varied widely, between $20 to $80.
But be mindful to match the fob frequency. My fob's external label had rubbed off along with the frequency number, but it is also printed inside; which is accessible as if you are changing the fob battery.