How Am I Doing?

Sounds like a good start.

What happens if your paper wallet backup is lost/destroyed? (Think building fire)

You can backup your .wallet file if you are worried about losing the labels for your transactions/addresses. If you back it up, make sure the backup is not a security risk.

That should be it for stuff to backup. Everything else you can just download a new copy if needed.

Don't install windows updates on you cold storage laptop. The whole idea of cold storage is security via an air gap. You don't need to worry about viruses/trojans/worms/etc. on you cold storage machine because it is not connected to the internet. The only way that data should get to it is via a USB drive or CD-R.

Other thoughts: Make sure the cold storage laptop is really and truly offline. I recommend disabling auto-play for both USB and the CD drive. If possible uninstall the Ethernet/wifi/Bluetooth driver. If there is a hardware switch to disable the wireless/Bluetooth, set it to the off position. Consider filling the Ethernet port with epoxy or gum. Consider filling any other ports (Firewire, thunderbolt, serial, parallel, etc.) with epoxy or gum. Lock the BIOS with the harddrive as the first boot device. Have you thought about the physical security of the cold storage laptop (could somebody re-install the operating system without you noticing)?

Most of the comments under "Other thoughts" get into pretty extreme paranoia, but depending on how many bitcoins you have it might be worth it.