Here is an approach that looks different from Jeremy Daniel's one, so may be worth writing:
The idea is simply that $y$ being transcendental over $K$, it acts as a free variable, and by Gauss Lemma, reducibility in $K(y)[t]$ is equivalent to reducibility in $K[y][t]$, the polynomial ring in variables $y,t$.
Let $y := f(x)/g(x) \in K(x)$, with not both $f,g$ in $K$, so that $y\notin K$.
Let $p(t) := f(t) - yg(t) \in K(y)[t]$.
$x$ is transcendental on $K$:
By construction.
$x$ is algebraic on $K(y)$:
Since $p(x) = 0$.
$y$ is transcendental on $K$:
By multiplicativity of degrees of extensions:
$$
\underbrace{[K(x):K]}_{\infty} = \underbrace{[K(x):K(y)]}_{<\infty}[K(y):K].
$$
The polynomial $p(t)$ has degree $n:=\max(\deg f,\deg g)$:
Since the coefficients of $f$ and $g$ don't cancel out (if $f(t) =\sum_i a_i t^i$ and $g(t) = \sum_i b_i t^i$, then $f(t) + yg(t) = \sum_i (a_i + yb_i)t^i$, and $y\notin K$ implies that $a_i + yb_i =0$ iff both $a_i,b_i=0$).
The goal is to show that $p(t)$ is irreducible in $k(y)[t]$, which will imply it is the minimal polynomial for $x$, hence the degree of $x$ is equal to $n$.
$p$ is reducible in $K(y)[t]$ iff it is in $K[y][t]$:
By Gauss Lemma, since $K(y)$ is the field of fractions of $K[y]$.
$K[y][t]$ is the ring of polynomial in two variables over $K$:
Obvious since $y$ is transcendental over $K$.
Now, we consider the polynomial $p(y,t) = f(t) + yg(t) \in K[y,t]$.
If it is reducible, say $h(y,t)k(y,t) = p(y,t)$, then necessarily the "$y$-degree" (=highest occurence of $y$ -- I don't know the usual term) of $h$ is $0$, and that of $k$ is $1$ (wlog), so we may write $h(y,t) = h(t)$ and $k(y,t) = k_1(t) + yk_2(t)$.
Multiplying this yields:
$$
h(t)k_1(t) + yh(t)k_2(t) = f(t) + yg(t),
$$
and by comparing coefficients,
$$
h(t)k_1(t) = f(t),\qquad h(t)k_2(t) = g(t),
$$
hence $h$ divides both $f$ and $g$, contradicting coprimality.
$F(\alpha)$ means the smallest field containing both $F$ and $\alpha$.
$\gamma$ algebraic over $F$ means that there is a non-zero polynomial $p(X) \in F[X]$ (i.e., a polynomial with coefficients in $F$) with $p(\gamma) = 0$. (And transcendental means such a polynomial does not exist).
Now the problem itself. The situation is as follows.
Since $\alpha$ is algebraic over $F(\beta)$, there is a non-zero polynomial $f(X) \in F(\beta)[X]$ with $f(\alpha) = 0$. The coefficients are elements of $F(\beta)$, but clearing denominators we may as well assume they are elements of $F[\beta]$.
So, $f(\alpha)$ is a polynomial expression in both $\alpha$ and $\beta$ and we can see it as a polynomial expression $g(\beta)$ in $\beta$ with coefficients in $F[\alpha]$, i.e., $g(Y) \in F[\alpha][Y]$. (To be precise, there is a polynomial $h(X,Y) \in F[X,Y]$ such that $f(X) = h(X,\beta)$ and $g(Y) = h(\alpha,Y)$.) Now $0 = f(\alpha) = g(\beta)$.
What is still left to show is that $g(Y)$ is not the zero polynomial, i.e., that not all its coefficients are $0$. But its coefficients are of the form $c(\alpha)$ with $c(X) \in F[X]$ and because $\alpha$ is transcendental over $F$, $c(\alpha)$ is $0$ only if $c(X) = 0$. So, if $g(Y)$ were the zero polynomial, so would $f(X)$ be.
Example. Take $\alpha = T^2$ and $\beta = T^3$ in the field ${\mathbb Q}(T)$ of rational functions over ${\mathbb Q}$. Then $\alpha$ is transcendental over ${\mathbb Q}$. Also, $\beta$ is algebraic over ${\mathbb Q}(\alpha)$ as it satisfies $\beta^2 - \alpha^3 = 0$ (i.e., $\beta$ is a root of the polynomial $Y^2 - \alpha^3$ over ${\mathbb Q}(\alpha)$). Exactly the same relation shows that $\alpha$ is algebraic over ${\mathbb Q}(\beta)$ (as $\alpha$ is a root of the polynomial $\beta^2 - X^3$ over ${\mathbb Q}(\beta)$).
Best Answer
The confusion is really that polynomials are used in two differerent ways here. Given any ring $A$ and a polynomial $f(y)\in A[y]$, and any element $a\in A$, we can "evaluate" the polynomial $f$ at $a$ such that $f(a)\in A$. This is either due to the fact that polynomials are formed with addition and multiplications that can be performed in any ring, or the universal properties of polynomials.
Now, in this particular case, $A=F(x)$ and the coefficients are restricted to the subring $F$, hence $f(y)$ is chosen to be in $F[y]$ and $x$ is the formal variable from $F(x)$, we have the evaluation $f(x)$ is equal to itself as a polynomial. Now we have the identity $f(x)=0$ not in $F$ but in $F(x)$ (equivalently to in $F[x]$, as $F[x]$ is a domain), because $A=F(x)$, and it just happens that all coefficients are in $F$. And finally two polynomials are equal iff they have all the same coefficients.
In other words, the polynomial say $1+x+x^2\in\mathbb Q[x]$ can be regarded as an entity that is just an element of $\mathbb Q[x]$, but it can also be considered the result of $1$ plus $x$ plus $x$ times $x$ in the ring $\mathbb Q[x]$.