Block ciphers, AES is a block cipher, encryption $Enc$ can be formalized as
$$Enc:\mathcal{P} \times \mathcal{K} \to \mathcal{C}$$ where $\mathcal{P}$ is the plaintext space, $\mathcal{K}$ is the keyspace, and $\mathcal{C}$ is the ciphertext space. Similarly the decryption; $$Dec :\mathcal{C} \times \mathcal{K} \to \mathcal{P}.$$ For a block cipher the $\mathcal{P} = \mathcal{C}$. The number of elements of this space is determined by the bits, for $\mathcal{P}$ it is determined by the block size. AES has 128-bit block size and it has $2^{128}$ message space for a single block. For DES it is $2^{64}$. AES has variable key sizes like 128,192, and 256, therefore, the keyspace $\mathcal{K}$ is $2^{128},2^{192},\text{ and } 2^{256}$, respectively.
We require the operation of a block cipher invertible[*] so that we can decrypt. Therefore the block ciphers are permutations. Each key from the keyspace selects a permutation for all possible permutations. The number of permutations of the message space is $2^b!$ where $b$ is the block size and for AES this is $2^{128}!$. With the Stirling's approximation $$2^{128}! \approx \sqrt{2\pi 2^{128}}(\frac{2^{128}}{e})^{2^{128}}.$$ That cannot be covered by the tiny keyspace $2^{128}$, tiny according to comparison, but huge for any classical computational power.
We expect that a block cipher behaves like a Pseudo-Random Permutation that is a function that cannot be distinguished from a random permutation and AES has believed to be one.
Back to your questions;
- What is the concrete step(s) of AES (or a similar popular symmetric key encryption algorithm) that makes encrypting an n-byte plaintext with an n-byte key not the same as a One Time Pad?
Block ciphers use the confusion diffusion paradigm, Shannon 1945. Here, what related to your approximation is, changing one bit of the key will affect all ciphertext bits. If the cipher achieves the avalanche effect property then it will randomly flip half of the bits. Therefore all of the bits of the block are affected (affected doesn't mean changed) whereas in OPT changing one bit only affects one plaintext bit.
- It feels intuitive that if the key is shorter than the plaintext, then all plaintexts cannot be possible regardless of the algorithm. The other way around (key longer than the plaintext) is not intuitive.
It is not all of the plaintexts, it is all of the permutations. In AES. all of the 128 bits are valid plaintext and plaintext space contains all. But block ciphers randomly select permutations from all possible permutations space. With the keyspace, we cannot cover all of the permutations. They are limited to keyspace.
This the distinction between the OTP and AES or any block cipher. In block ciphers, the key size is fixed no matter the length of the plaintext. In block ciphers, We use computational security since we cannot achieve informational security without key bits equal to message bits.
- If the question is if the key is as large or larger than the plaintext, then why can AES be distinguished from a perfect cipher?
There is no guarantee that given a ciphertext $c$ decrypted under all possible keys $c=AES_k(x)$ gives all possible plaintexts or gives all but they are equally distributed. This is contradicting to perfect secrecy that OTP has.
To prove that AES has perfect secrecy in this sense, we need to fully analyze the AES. This is beyond our computation point. If possible, it may lead to a known-plaintext attack.
While it is reasonable property of a block cipher that reaches all possible plaintext, equally, most block ciphers try to approximate random permutation where each key is independent of the others. This means that we may not reach all plaintext with decryption of $c=AES_k(x)$ under all keys. Or similarly, possibly there are plaintexts where $E_{k_1}(c)=E_{k_2}(c)$.
[*] Block cipher need modes of operation, and not all modes require decryption, like CTR mode. In CTR mode, one can use Hash functions that are not permutations.
