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."
The approach taken in this proof is similar to the proof of Theorem 3 in Section 5.2 of Ireland, Rosen: A Classical Introduction to Modern Number Theory. This theorem states that for every non-square integer $a$ there are infinitely many primes $p$ such that $a$ is a quadratic non-residue modulo $p$.
$\newcommand{\jaco}[2]{\left(\frac{#1}{#2}\right)}$Let $q=p_k$ be the $k$-th prime, we also consider all smaller primes $p_1=2<p_2<\dots<p_{k-1}<p_k$. We want to find $p$ such that $$\jaco 2p=\jaco{p_2}p = \dots = \jaco{p_{k-1}}p = 1 \qquad\text{a}\qquad \jaco{p_k}p=-1. \tag{*}$$ If there is such $p$, then
Since the smallest quadratic non-residue must be prime, we get that $p_k$ the smallest quadratic non-residue modulo $p$.
To get a prime which fulfills $(*)$, we consider the system of congruences \begin{align*} p &\equiv 1\pmod8\\ p &\equiv 1\pmod{p_2}\\ &\vdots\\ p &\equiv 1\pmod{p_{k-1}}\\ p &\equiv s\pmod{p_k} \end{align*} where $s$ a is some quadratic non-residue modulo $p_k$.
First, this system of congruences is equivalent to $p\equiv a \pmod{8p_2\cdots p_k}$ for some $a$, i.e., the solutions form an arithmetic progression. Moreover, it is easy to see that $\gcd(a,8p_2\cdots p_k)$, since $a$ fulfills all congruences listed above. So we get from Dirichlet's theorem that there is a prime number $p$ which fulfills this system of congruences.
For any such prime we have $$\jaco2p=1,$$ since $p\equiv 1\pmod 8$. At the same time, using law of quadratic reciprocity together with $p\equiv1\pmod4$ we get $$\jaco{p_i}p=\jaco{p}{p_i}=\jaco1{p_i}=1.$$
Similarly, we have $$\jaco{p_k}p=\jaco{p}{p_k}=\jaco s{p_k}=-1.$$