What is the difference between a wallet and paired keys? So I've read that a wallet is basically a public address key paired with a private key.

But is it more than that?   Does the physical wallet file contain transaction and balance information as well or does that get pulled from the cloud?

For example, let's assume I have just the public and private keys written down on a piece of paper...

If I import those keys into a wallet client, will the wallet client download my balance and transaction history associated with my address from the cloud?
Yes. The cloud you're referring to is actually the block chain. A bitcoin wallet has various different meanings, such as web-wallet, brain wallet, or various others, but in my opinion the best representation of a wallet is actually a file, commonly a wallet.dat file. Then you use a bitcoin client to open this wallet file.

Inside this file there's various key pairs that you can use to make bitcoins transactions. No balance information is kept in this file otherwise it would be extremely large in size. 

The important part is that a bitcoin wallet's format is not standardized. This means that each bitcoin client implements its own wallet file format. You can't import Bitcoin-QT's wallet file in Multibit for example.

But again, a wallet can be represented in a variety of different ways: as files, on the web managed by third parties, as a piece of paper, etc.