What is the difference between a wallet and paired keys?
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.