What you need to understand is the concept of change addresses. A bitcoin transaction consumes one or more previous outputs (coins sent to you) as inputs. It's impossible to spend part of an input, the same way that you couldn't cut off a piece of a $100 bill for payment. You'd need to spend the entire $100 bill, and you'd get change back. The way this is handled with bitcoins is that the transaction that spends one or more previous input, if the wallet doesn't have "exact change", will have more than one output -- in other words, you're sending bitcoins to two different places. There will be an output in the amount that you sent, to the address that you specify, and there will be an output back to you, which is the difference between the outputs that you spent and the amount that you sent to somewhere else (plus the fee, if applicable). The output back to you is sent to an address that Bitcoin-Qt automatically generates, and is not shown to you. For that reason, with paper wallets, once you've imported the key into a wallet, that paper wallet should be considered useless and be destroyed, because once you spend even part of it, the remainder does not necessarily stay in the paper wallet, but is transferred to a client-generated change address. Change addresses that the client has generated will not be shown in the interface. If you'd like to confirm that a change address belongs to you, you can use the "validateaddress" RPC command in the debug console, which will return "isMine":"true" or something to that effect. I highly recommend that you read the wiki's article on change,
https://en.bitcoin.it/wiki/Change, for more detailed explanation.
Now, to your situation.
It seems to me that your paper wallet was not funded all at once, but rather in several smaller transactions of a few bitcoins each. What happened here is that after you imported the key from the piece of paper into your wallet, when you sent the small transactions, it spent some, but not all, of the outputs controlled by the paper wallet's key. The remainder of those outputs were transferred into change addresses within your B-Qt wallet. Three outputs, in the amounts of 4.8926 BTC, 0.00945727 BTC, and 0.008 BTC, remained unspent. Those outputs were swept up by Coinbase, and transferred to them.
In the meantime, your client believed that it had ~10 BTC available to it -- ~4.91 from the paper wallet's key, and ~5 from the assorted other keys in the wallet, including those change addresses that I mentioned. Presumably the client was offline at the time that the key was swept by Coinbase, and subsequently was started, and then while it was still busy syncing and catching up to the network, the bitcoins were sent in a transaction to Coinbase. The client, not having been up-to-date enough to see the paper wallet key swept by Coinbase, didn't realize that those outputs were no longer unspent, and tried to spend them along with the other coins that it did have control over. This transaction was rejected and not relayed by other nodes, which see it as an invalid transaction, since it's trying to spend coins that have already been spent. Now, your client will continue to hold on to this transaction in its wallet and try to rebroadcast it periodically, to no avail. What you need to do is clear that invalid transaction. If you're willing to lose metadata (address labels, etc) attached to the wallet, you can start Bitcoin-Qt with the -salvagewallet flag, which will cause it to make a new copy of your wallet, transferring over only keypairs, and leaving behind everything else, which includes the transactions. At that point, it will perform a rescan, and scan the blockchain for any relevant transactions. Once that's done, it should show your correct balance. This is probably the easiest way to solve your problem. Other possible ways would include editing the wallet file (it's simply a BDB database) to remove the invalid transaction, or manually creating a transaction that will spend the outputs that are currently locked up in the invalid transaction.
