This answer is meant to answer only your second question.
Claim. Let $K=\mathbb{Q}(\sqrt[3]{2})$ and $\alpha = \sqrt[3]{2}-\sqrt[3]{4} \in K$. Then there does not exist $\beta \in K$ such that $\beta^2-\alpha \in \mathbb{Q}$.
More generally, any square in $K=\mathbb{Q}(\sqrt[3]{d})$ is of the form
$$
(x+y\sqrt[3]{d}+z\sqrt[3]{d^2})^2=x^2+2dyz+(2xy+dz^2)\sqrt[3]{d}+(y^2+2xz)\sqrt[3]{d^2}.
$$
So, if for every $\alpha \in K$ there exists $\beta \in K$ such that $\beta^2-\alpha \in \mathbb{Q}$, that means that for every $b,c \in \mathbb{Q}$ there exist $x,y,z \in \mathbb{Q}$ satisfying
$$
2xy+dz^2 = b,~~y^2+2xz=c.
$$
This is an intersection of two quadrics in three-dimensional space, which defines a curve of genus $1$ if it is non-singular. Eliminating $x$, we obtain
$$
bz-dz^3=cy-y^3,
$$
which is a plane cubic curve with the rational point $P=(0,0)$ on it (which on the intersection of the two quadrics corresponds to the point at infinity).
In fact $P$ is a flex or inflection point, meaning that the tangent to $P$ (which is simply given by the linear part of the equation of the curve, so by $cy-bz=0$) has intersection multiplicity $3$. Considering the equation of the cubic in homogeneous form,
$$
bX^2Z-dZ^3=cX^2Y-Y^3,
$$
the coordinates of the point $P$ are now $(1:0:0)$ and its tangent is $cY-bZ=0$. If you look in Cassels' book on elliptic curves, you find that you can transform a cubic with a flex $P$ into Weierstrass form by a linear transformation which maps $P$ to the point $(0:1:0)$ and its tangent to the line $Z=0$. The first can be achieved by just interchanging the roles of $X$ and $Y$, i.e. by considering the new curve
$$
bY^2Z-dZ^3=cXY^2-X^3,
$$
where now the point $P$ has coordinates $(0:1:0)$ and tangent equal to $cX-bZ=0$. If we further replace $Z$ by $(cX-Z)/b$, we will obtain a Weierstrass curve (up to a simple scaling of $X$ and $Y$). The substitution $Z \mapsto (cX-Z)/b$ yields $Y^2(cX-Z)-d(cX-Z)^3/b^3=cXY^2-X^3$, where you already see the $XY^2$ terms cancelling each other, producing the equation $-b^3 Y^2Z - d(cX-Z)^3=-b^3 X^3$, or after rearranging terms $b^3 Y^2Z = b^3 X^3 - d(cX-Z)^3$. Now we change back to affine coordinates $x$ and $y$, and we obtain $b^3 y^2 = b^3 x^3 - d(cx-1)^3$. We expand and collect the cubic terms:
$$
b^3 y^2 = (b^3- c^3d) x^3 + 3c^2dx^2 - 3cdx + d.
$$
We get rid of the coefficients of the highest powers in $x$ and $y$ by multiplying everything by $b^3(b^3- c^3d)^2$ and replacing $x \mapsto x/(b(b^3- c^3d))$ and $y \mapsto y/(b^3(b^3- c^3d))$. We then get:
$$
y^2 = x^3 + 3bc^2dx^2 - 3b^2cd(b^3- c^3d)x + b^3d(b^3- c^3d)^2.
$$
Now this is a Weierstrass curve which is isomorphic (even projectively equivalent) to the cubic curve we started with, so in the case where it has no other points except $(0:1:0)$, we will know that the original system of two quadratics has no solutions. (Also conversely, if it does have non-trivial points, then the system does have a solution.)
For this, we can use for example Sage. When we do that, for example putting as I did $d=2$, $b=1$, $c=-1$, we will find that the resulting Weierstrass curve is $y^2=x^3+6x^2+18x+18$, and that its group of rational points is the trivial group. $\square$
The answer to the part "How does one determine whether there exists $\beta$ such that $\beta^2-\alpha \in \mathbb{Q}$?" probably has to be that one simply has to solve the equations (which means finding points on a curve given as the intersection of $d-1$ quadrics in $d$-dimensional space). I don't think there is anything else for it. Even in the degree $3$ case there seems to be no short-cut available.
