I just want to see if my proof is correct. It goes this way:
Suppose $\alpha \in K$ is a root of $f$, with minimal polynomial $p_\alpha \in k[X]$. Then $k \subseteq k(\alpha) \subseteq K$ is a composition of field extensions, with $[K: k] = [K: k(\alpha)][k(\alpha): k] = p$. This implies that either $[K:k(\alpha)] = p$ and $[k(\alpha): k] = 1$ or $[K: k(\alpha)] = 1$ and $[k(\alpha): k] = p$. As the first already establishes the desired result, we suppose that $[K: k(\alpha)] = 1$ and $[k(\alpha): k] = p$. Then, $p_\alpha | f$, i.e., $f = gp_\alpha$ for some $g \in k[X]$. Because $\deg{f} = p+1$ and $\deg{p_\alpha} = [k(\alpha) : k] = p$, we can conclude that $\deg{g} = 1$. Polynomials of degree 1 always have roots in their field of coefficients, which implies that $g$, and hence $f$, has a root in $k$.
Is this correct? Can you answer more elegantly?