It is well known that if $p > 23$, then there exists a quadratic non-residue which is less than or equal to $\sqrt{p}$. For $k = 1,2$ we get that $-1,-2$ are quadratic residues, and hence $2$ is also a quadratic residue. For $k \geq \lfloor \sqrt{p} \rfloor$, $\left \lfloor \frac{p}{k} \right \rfloor$ takes all the values which are $\leq \sqrt{p}$, so this means all the odd positive integers which are less than $2\sqrt{p}-1$ are quadratic residues. Since $2$ is also a quadratic residue, we get that all the positive integers which are less than $2\sqrt{p}-1$ are quadratic residues. But this clearly contradicts the first sentence. So $p \leq 23$ and bashing gives that $p=2$ is the only solution.

Here's a full solution: Notice that $p=2$ is valid and assume that $p$ is odd. Let $k=1$ to get that $-1$ is a quadratic residue. Now, choose $k=\lfloor p/2\rfloor$ and use the latter to infer that $2$ is a quadratic residue as well. Notice that $\lfloor p/m\rfloor=n\iff p/(n+1)<m\leq p/n.$ Thus, if $n\leq\sqrt{p}-1$ we have $p/n-p/(n+1)\geq 1$ so there exists for sure some integer $m$ such that $\lfloor p/m\rfloor=n.$ It follows that $2i-1$ is a quadratic residue for all $1\leq i\leq\sqrt{p}-1.$ In other words, all prime numbers $q\leq 2\sqrt{p}-1$ are quadratic residues modulo $p.$ Now, by the transitivity of Legendre's symbol, we have \[\Bigg(\frac{\prod p_i^{a_i}}{p}\Bigg)=\prod\bigg(\frac{p_i}{p}\bigg)^{a_i}\]so we can conclude that all integers $1\leq n\leq 2\sqrt{p}-1$ are quadratic residues modulo $p.$ Now comes the crux of the problem: Lemma: For all odd prime numbers $p,$ the smallest non-quadratic residue is smaller than $\sqrt{p}+1.$ Proof: Let $n$ be the smallest non-quadratic residue. Let $m=n\big(\lfloor p/n\rfloor+1\big)-p.$ Observe that $0<m<n.$ Furthermore, we have\[\bigg(\frac{m}{p}\bigg)=\bigg(\frac{n\big(\lfloor p/n\rfloor+1\big)}{p}\bigg)=\bigg(\frac{n}{p}\bigg)\bigg(\frac{\lfloor p/n\rfloor+1}{p}\bigg)=-\bigg(\frac{\lfloor p/n\rfloor+1}{p}\bigg).\]Since $0<m<n,$ it must be a quadratic residue, by the minimality of $n$. Therefore, $\lfloor p/n\rfloor+1$ is a non-quadratic residue, so yet again, by the minimality of $n$ we get $\lfloor p/n\rfloor+1\geq n.$ The latter yields $n<\sqrt{p}+1,$ finishing the proof. Now, $p=3$ fails since $-1$ is not a quadratic residue modulo $3,$ and the odd primes $p\geq 5$ fail due to the lemma.