I've read several texts which say that if the entire plaintext is a multiple of the block-size padding is not required (and not using padding would not mean a loss of security). I generally disagree on this.
In modes where padding is used (e.g., CBC), padding is mandatory. This is per spec. Not including the padding is simply not an option.
In some special cases, for example in CTR of OFB mode padding could even unveil more information about the block-cipher output than not using it. But many currently used paddings are randomized.
It's a bit confusing what you're actually asking here, because CTR and OFB don't use padding, as they're stream ciphers. You could pad them (for instance, to make traffic analysis more difficult), but whether or not to do so is a decision completely independent of the block size of the underlying cipher. Padding to the block size is done for block modes like CBC.
When using a randomized padding with modern block ciphers the smallest change in the block-cipher input will change the entire block-cipher output.
For the final block only. Unless you pad at the front, which isn't done by any modes I'm aware of. For streaming modes of block ciphers, padding doesn't change any of the bits of the actual ciphertext. Unless, again, you pad at the front.
Therefore the randomness of the padding contributes to the encryptions security.
No, not even slightly. Even if you did pad at the front of a block cipher and get a completely new ciphertext as a result, this doesn't directly contribute the security of the block cipher in the least. If the block cipher was secure beforehand, you simply have a different stream of bits that are equally secure. If the block cipher was insecure beforehand, you still have a stream of bits that is (generally) going to be vulnerable to the same set of attacks as before.
Padding like this might change some bits, but it doesn't improve the actual security of the cipher. In fact, some times, it can weaken it (see CBC padding oracle attacks). Padding in block ciphers isn't done for security, it's done because block-sized inputs is required by the underlying block cipher.
My first question is whether the above statement is correct or not and why. And second: Are modes like CBC/PCBC more secure than modes like CTR/OFB? Or does it depend on the used padding?
Your question doesn't really make sense as asked. These modes have different security properties and fail in different ways. CBC can fail catastrophically to padding oracle attacks because of its padding. CTR can fail catastrophically when IVs are reused, but padding won't help solve this problem. Both are equally secure when used correctly, but CBC is somewhat harder to use correctly in common use-cases.
