Your options will depend on your technical skill, but really it is safer and easier to just think of any paper wallet that you "redeem" as being compromised and simply create a new paper wallet to send the remaining balance to.
As soon as you send any bitcoins that were received at an address, that address immediately becomes a bit less secure. In general, especially for short term use, this slight reduction isn't significant, but given the ease of creating a new address, why not make it as secure as you can.
Technical note for those who would like to know why an address is a bit less secure after spending bitcoins received at that address:
Bitcoins stored at an address that has never sent any bitcoins anywhere have three levels of cryptography between the private key and the publicly available bitcoin address (ECDSA, SHA-256, and RIPEMD-160). Once you spend bitcoins from an address the public key of the address becomes public knowledge. After that the only layer of security is the ECDSA algorithm between the private key and the public key. This means that if a weakness is ever discovered in the ECDSA algorithm, bitcoins that are stored at addresses that have previously sent bitcoins will become vulnerable to the weakness. Meanwhile, the bitcoins that are stored at addresses that have only ever received bitcoins are not vulnerable unless weaknesses are simultaneously discovered in all three algorithms.
As soon as you send any bitcoins that were received at an address, that address immediately becomes a bit less secure. In general, especially for short term use, this slight reduction isn't significant, but given the ease of creating a new address, why not make it as secure as you can.
Technical note for those who would like to know why an address is a bit less secure after spending bitcoins received at that address:
Bitcoins stored at an address that has never sent any bitcoins anywhere have three levels of cryptography between the private key and the publicly available bitcoin address (ECDSA, SHA-256, and RIPEMD-160). Once you spend bitcoins from an address the public key of the address becomes public knowledge. After that the only layer of security is the ECDSA algorithm between the private key and the public key. This means that if a weakness is ever discovered in the ECDSA algorithm, bitcoins that are stored at addresses that have previously sent bitcoins will become vulnerable to the weakness. Meanwhile, the bitcoins that are stored at addresses that have only ever received bitcoins are not vulnerable unless weaknesses are simultaneously discovered in all three algorithms.
Thanks for the info.
