It depends on how large the image $U$ of the global units $\mathcal{O}_K^\times$ in the group $$\prod_\sigma (\mathcal{O}_K/(\sigma(q)))^\times$$
happens to be. It's almost never the full group (because the unit rank is always smaller than the field degree), and in general it will be very far from it.

In the rare case when $U$ is all of that, you can multiply $q$ by a unit to move its images in the other factors (i.e. $\sigma \neq \mathrm{id}$) anywhere you want without changing the prime ideal it generates. But usually $U$ will be much smaller, even when $\mathcal{O}_K^\times$ happens to surject onto each factor $(\mathcal{O}_K/(\sigma(q)))^\times,$ and certainly when it doesn't. For an example, take $K=\mathbb{Q}(\zeta_4)$ and $p=17$: you only have the fourth roots of unity available to adjust $q$. The image of $q=4+\zeta_4$ in the other residue class field $\mathcal{O}_K/(4-\zeta_4)$ is $8$, and you can move it to any of $-2, -8, 2$; but these are all quadratic residues.

All this is not yet a complete answer - it also depends on how, as $p$ varies, the subgroups of $\mathbb{F}_p^\times$ fit into the additive structure of $\mathbb{F}_p$. But in general I expect you'll find that few $p$ will work.