Spending a paper wallet means bringing the entire balance online. The right way to do cold storage is with offline signing.
What's offline signing?
Generating transactions offline (without loading the keys in a connected wallet). You basically sign the transaction you want (send X amount to destination, the rest to yourself) with the private key (yourself) and public key (destination).
You then copy-pasta this transaction string (it's a long hex-encoded string like 3045022100c769e22e360f1bea319deab8cab482aeec6174da1dae206875f73245d579c8da02202
551c09708cad964e57b1f3068e96121870604d77cb46252dcb0d6f97ea1b61501 04dd7aac2e04d643e4a95d1a0ad0df3ab6eea1aeff0284aaad2f4eec6540922e640e717f1ac2d1f
2bf1664bb08b35d19f5eee909412621802c2669d77ced6a7703 ) onto a connected bitcoin client, and broadcast it to the network.
At this point, the transaction is checked and relayed by your peers. Please note that the offline client can't have the latest blockchain and tx pool from the live network and it won't validate your transaction. After you transaction is approved online, any inputs used in it on the offline client will be useless for new transactions.
The best way to do this is to connect a live client to the internet and update the blockchain, take a snapshot or clone the OS, take instance offline, load private keys or wallet, generate the transaction, save transaction, new private keys and new wallet, destroy instance, broadcast transaction.
Note that if you don't send paper wallet change to yourself or you don't save wallets correctly, you could lose the remainder of the bitcoins that you send to yourself.