Why do Problems for Post-Quantum algorithms have to be NP-Hard? The mathematical problems used for Post-Quantum Cryptography problems I came across, are NP-complete, e.g.

Solving quadratic equations over finite fields
short lattice vectors and close lattice vectors
bounded distance decoding over finite fields

At least the general version of these is NP-complete
I am asking myself why these mathematical problems need to be NP-complete (in the general version) and how this is even useful, when instances are used that are not NP-complete
I am unaware of cryptography that is hard solely assuming that $P\neq NP$, so I believe you are misunderstanding something. I know the story best when it comes to lattices, so I'll discuss why lattices are solely &quot;adjacent&quot; to an $NP$-hard problem.
The story is rather simple, but also technical.
Let $\mathsf{LWE}[n, \sigma, q]$ be the average-case LWE problem in dimension $n$, standard deviation $\sigma$, and moduli $q$.
Regev's quantum worst-case to average-case reduction for LWE states that:
$$\mathsf{SIVP}_{\tilde{O}(nq/\sigma)} \leq \mathsf{LWE}[n, \sigma, q]$$
Where $\mathsf{SIVP}_\gamma$ is the short independent vectors problem (think of it like a generalization of the shortest vector problem to finding $n &gt; 1$ short linearly independent vectors, where $n$ is the dimension of the lattice).
Note that the $\gamma$ here is an approximation factor that is allowed in the problem.
What is the precise complexity of $\mathsf{SIVP}_\gamma$?
This highly depends on the parameter $\gamma$, but the following should suffice for this post.
It is known that $\mathsf{SIVP}_{\tilde{\Omega}(\sqrt{n})}$ is in $\mathsf{AM}\cap co\mathsf{AM}$.
This implies that it is not $\mathsf{NP}$-hard unless the polynomial hierarchy collapses to some finite (it looks like 2nd?) level, which complexity theorists view as being unlikely.
This essentially means that while $\mathsf{SIVP}_\gamma$ is known to be NP-hard for some $\gamma$, the $\gamma$ used in lattice cryptography is such that we view it as extremely unlikely that $\mathsf{SIVP}_\gamma$ will be NP-hard.
Still, for basic protocols one can generally take $\gamma$ to be some small polynomial, so $\mathsf{SIVP}_\gamma$ is &quot;close&quot; to an NP-hard problem, especially as the smallest approximation factor that we have polynomial-time algorithms for is something sub-exponential iirc.
More generally, NP hardness is the wrong thing to look at in cryptography.
What people actually want is some notion of average-case hardness.
In lattice cryptography one can formally connect that with worst-case hardness, but not every area in cryptography has such reductions.
In areas that don't, the particular worst-case hardness of the problem is not very important --- a problem can have some instances that are very hard while still being bad for cryptography, as it may be hard to generate a hard instance.
What is more important is specifying some plausible average-case hard distribution and examining the particular hardness of this.