download the webpage
https://www.bitaddress.org/take your computer offline ( remove the internet wire )
load a linux live boot cd/usb.
print out a public/private key pair using that bitaddress webpage.
you've got yourself cold storage.
You forgot to mention something else here... If the computer was infected with malicious code that logs all Bitcoin addresses, then whatever
Bitcoin address or paper wallet you created, would be logged. There are even Malware that scans the print buffer on printers, after you
used that printer. So, I would rather use a Air-gapped computer & printer to print your paper wallets. { Do not connect them to the internet,
if you want to use them for large amounts of bitcoins. }