As it turned out by the end of the day, this question admits an exhaustive answer: for ${\mathbb Q}(\zeta_p)$ to contain an algebraic integer $\alpha$ with $|\alpha|=\sqrt{(n\pm\sqrt p)/2}$ (whatever the sign is), it is necessary and sufficient that for every prime $q$ dividing $p-1=(n^2-1)/2$ to an odd power, the order of $q$ modulo $p$ were also odd. This can be shown by interpreting $|\alpha|^2$ as the norm of $\alpha$ from the cyclotomic field ${\mathbb Q}(\zeta_p)$ down to its real subfield ${\mathbb Q}(\zeta_p)\cap{\mathbb R}$, and applying the Hasse norm theorem which says that if $\mathbb K$ is a cyclic extension of a number field $\mathbb L$, then an element of $\mathbb L$ is the norm (from $\mathbb K$ to $\mathbb L$) of an element of $\mathbb K$ if and only if it is a norm locally everywhere. Indeed, necessity can be established using a simple argument not based on the Hasse theorem.
Details can be found here (see Proposition 2 in the Appendix).