Are Bitcoins contained associated with a wallet or with an address in a wallet? What I want to know is, if I have a wallet with several addresses containing 10 BTC (let's say 1 BTC per address) in total and I want to send 5 BTC to a person, but first generating a new address (as this is advised for privacy reasons). What happens then? 

Are the Bitcoins from 5 random addresses first accumulated into the address I just generated, after which I can then use it to send the money to the receiving party?

Or how does it work?
Bitcoins are associated with Unspent Transaction Outputs (utxo). A UTXO contains a script that defines the terms under which it may be spent. Usually, this terms are as simple as "sign with correct private key", where said private key is associated with an address.

If you create new addresses in your wallet, your coins are not moved. When you want to spend five of the bitcoins from your example, you'd end up using-up five UTXO with a balance of one bitcoin each.

If you'd want to collect them in one address first, you'd have to send five bitcoins to the new address you created, i.e. actively send them to yourself.

I don't think that you'd increase your privacy by much, if you just sent the coins to yourself and immediately pass them on. Maybe a bit more plausible deniability, but not really much (because it would be curious that you'd just received five bitcoins from somebody else in the moment when you sent them on their way again).

What is commonly meant with the "new address for each transaction" paradigm, is that you never give out the same address for receiving a transaction twice. To wash coins by sending them to yourself, you'd probably want to send them to yourself several times and split them up in a bunch of different ways. However, if a good number of the outputs were then spent together in one transaction again, it would be obvious that you had split them up yourself anyway.