I couldn't resist trying to code up the algorithm hinted at in my comment.
Sage code at:
https://pastebin.com/3ANkqfZp
This is v2 of the code; version 1 used only prime-degree endomorphisms, and thus failed to distinguish between the orders $\mathbf{Z}[\sqrt{-15}]$ and $\mathbf{Z}[\tfrac{1 + \sqrt{-15}}{2}]$ (since the sets of primes arising as norms of elements in these two rings are the same). So it failed on $y^2 = x^3 + x + 8$ over $\mathbf{F}_{19}$. The new implementation uses endomorphisms of all degrees (piecing them together from isogenies of prime degree).
For instance, here we recover the values of $c$ in the table from p.303 in your linked article, using the functions defined in the script linked above:
sage: listofcurves = []
sage: K = GF(7)
sage: for a in K:
....: for b in K:
....: if 4*a^3 + 27*b^2 == 0:
....: continue
....: E = EllipticCurve([0, 0, 0, a, b])
....: if not any(E.is_isomorphic(F) for F in listofcurves):
....: print(E.ainvs(), endomorphism_conductor(E))
....: listofcurves.append(E)
(0, 0, 0, 0, 1) 1
(0, 0, 0, 0, 2) 1
(0, 0, 0, 0, 3) 1
(0, 0, 0, 0, 4) 1
(0, 0, 0, 0, 5) 1
(0, 0, 0, 0, 6) 1
(0, 0, 0, 1, 0) 2
(0, 0, 0, 1, 1) 1
(0, 0, 0, 1, 3) 1
(0, 0, 0, 1, 4) 1
(0, 0, 0, 1, 6) 1
(0, 0, 0, 3, 0) 1
(0, 0, 0, 3, 1) 2
(0, 0, 0, 3, 2) 3
(0, 0, 0, 3, 3) 1
(0, 0, 0, 3, 4) 1
(0, 0, 0, 3, 5) 3
(0, 0, 0, 3, 6) 2
PS: Important caveat: this computes the endomorphisms of $E$ over the given field $k$ (not over $\overline{k}$). If $E$ is ordinary this makes no difference (all endomorphisms are defined over $k$). In the supersingular case, it makes a difference: if $E$ is supersingular, but $\operatorname{Frob}_E$ isn't in $\mathbf{Z}$, we don't get a quaternion order, but an imaginary quadratic order (the centraliser of the Frobenius in $\operatorname{End}_{\overline{k}}(E)$). If $E$ is supersingular and the Frobenius is an integer, which can only happen if $k$ has even degree over its prime field, then the algorithm fails.
An elliptic curve $E$ over $\overline{\mathbb{Q}}$ can be defined over $\mathbb{Q}$ if and only if its j-invariant $j(E)$ is a rational number. More precisely, $E$ can be defined over a number field $K\subset \overline{\mathbb{Q}}$ if and only if $j(E)\in K$.
As Mathmo123 points out above, you can find many elliptic curves over $\mathbb{Q}(i)$ which can not be defined over $\mathbb{Q}$:
https://www.lmfdb.org/EllipticCurve/2.0.4.1/?field=2.0.4.1&Qcurves=non-Q-curve
But, it is actually quite easy to find examples yourself. Consider the elliptic curve $y^2 = x^3 + Ax + 1$. For which $A$ is the $j$-invariant a rational number?
Additional remark: If $\lambda\in \overline{\mathbb{Q}}\setminus \{0,1]\}$, then the Legendre elliptic curve $E_{\lambda}$ is defind by $y^2 = x(x-1)(x-\lambda)$. If $\lambda$ lies in $K$, then it is obviously defined over $K$.
The $j$-invariant of $E_{\lambda}$ is given by
$$ j(E_{\lambda}) = \frac{256(1-\lambda(1-\lambda))^3}{(\lambda(1-\lambda))^2} = \frac{256(1-\lambda+\lambda^2)^3}{\lambda^2 (1-\lambda)^2}. $$ So, $E_{\lambda}$ is defined over $\mathbb{Q}$ if and only if there is a rational number $q$ such that $$q\lambda^2(1-\lambda)^2 - 256(1-\lambda+\lambda^2)^3 =0. $$ So, choosing $\lambda $ (for example) to be an eleventh root of $2$ obviously gives a non-rational $j$-invariant. (Because this $\lambda$ does not satisfy a polynomial relation over $\mathbb{Q}$ of degree smaller than $11$.) So, this is a relatively easy way of writing down elliptic curves which can not be defined over the rationals.
Best Answer
By complex multiplication, the set of $j$-invariants of isomorphism classes of elliptic curves $E/\mathbb{C}$ with $\operatorname{End}(E) = \mathcal{O}_K$ is exactly $$ \{j(\mathfrak{a}) : \mathfrak{a} \in \mathcal{Cl}(\mathcal{O}_K)\}$$ ($\mathcal{Cl}$ denoting the ideal class group). Every element of this set has the same minimal polynomial. That minimal polynomial is the Hilbert class polynomial of $\mathcal{O}_K$, and the degree of the Hilbert class polynomial of $\mathcal{O}_K$ is equal to the ideal class number of $\mathcal{O}_K$. Hence the answer to your question is: There exists $E/\mathbb{Q}$ with $\operatorname{End}(E) = \mathcal{O}_K$ if and only if $\mathcal{O}_K$ has class number $1$.
There is an extensive body of literature on the class number $1$ problem which this post is too small to contain.