It is not difficult to check that the least quadratic nonresidue modulo prime $p$ cannot be a composite number, see, for example: Quadratic nonresidues mod p.
It is quite natural to ask the opposite question: Is every prime the least quadratic non-residue modulo some $p$? In the other words, if we are given a prime $q$, is there $p$ such that $q$ is a quadratic nonresidue modulo $p$ and, at the same time, all numbers $1,2,\dots,q-1$ are quadratic residues modulo $p$?
I think I have a proof which I outlined in my answer below. However, the proof uses Dirichlet's theorem on arithmetic progressions, which is rather non-elementary result. I was wondering whether there is a more straightforward solution.
I will also include link to the sequence A000229 in OEIS, which is described as: "a(n) is the least number m such that the n-th prime is the least quadratic nonresidue modulo m."