The message may be intercepted before. Isn't it a vulnerability allowing to discover the key?
No, for proper choice of key (see 1 below). AES-256 is designed to resist such Known Plaintext Attack. That's a standard hypothesis, and indeed $2^{256}$ is so immensely large that there's no worry to have that the key can be found by searching it (to put things in perspective, the waste of resources known as bitcoin mining so far has performed work equivalent to less than $2^{100}$ AES encryption). We're safe even if we hypothesize Cryptographically Relevant Quantum Computers ever become a thing.
The only protections one needs against key discovery in AES-256 are
- Choosing the key about uniformly randomly. A password won't do, key strechting won't cut it.
- Not disclosing it; see obligatory XKCD.
- Prevent it's extraction from any device it's inserted into. This is the hard part: how are you sure your PC is not infected by some trojan? And then there are side channel attacks and fault attacks.
Say, payload is 40 bit long. Since AES is working with 16 byte long block, would it make sense to add 11 bytes of random unique nonce or is this whole speculation not worth the effort?
There's another good reason to insert some randomness along the encrypted message: it's necessary to resist Chosen Plaintext Attack, and in particular prevent adversaries from testing if two plaintexts are identical merely by comparing their ciphertexts.
Also, notice that typical applications requiring confidentiality of the plaintext also require it's integrity, that is authenticated encryption, and straight AES encryption with common encryption-only block-cipher modes of operation won't give that even with random IV/nonce. Further, some applications require prevention against replay, and straight authenticated encryption won't give that.
Choosing a cryptographic algorithm is not something to do lightly. Sorry, but that should not be attempted by one having to ask the present question.
