Let $f(X) = \det(XI-\beta)$ as in the OP. (But $X$ is a transcendent variable.)
I will write $!K$ for the vector space over $\Bbb Q$ obtained from $K$ by applying the forgetful functor $!$, so $T:=(\beta I-\theta_\beta):!K\to !K$ is the zero morphism, so $\det T=0$. (We do not need Cayley-Hamilton. And moreover...)
This shows that assuming $f\in\Bbb Z[X]$, because also $f(\beta)=0$, the minimal polynomial of $\beta$ is a divisor of $f$, so it is in $\Bbb Z[X]$, gaussian Lemma, so $\beta$ is algebraic.
The converse, and the question.
Let us assume now that $\beta $ is algebraic.
Let $L$ be the subfield of $K$ generated by $\beta$ over $\Bbb Q$. Then $1,\beta,\dots,\beta^{k-1}$ is a basis of $!L$ over $\Bbb Q$, $k$ being the degree of $\beta$ over $\Bbb Q$.
Fix now some $x\in \Bbb Q$, and let us write the matrix of $$T(x):=(xI-\theta_\beta)\ ,\qquad x\in\Bbb Q\ ,$$ seen first as a morphism $!L\to\!L$, (later as $!K\to!K$,) w.r.t. this basis.
This matrix is $xI$ minus a companion matrix, and the companion matrix has only integer entries, since $\beta$ is algebraic.
Now consider a basis of $K:L$, and for each $\gamma$ in this basis the system $\gamma,\gamma\beta,\dots\gamma\beta^{k-1}$. The matrix of $T(x)$, restricted to the subspace generated by this system is again the same matrix, $xI$ minus integral companion matrix.
Pasting these system together, we get a basis of $K:\Bbb Q$, and the matrix of $T(x)$ is a diagonal repetition of the same block. Now $f(x) = \det T(x)$ holds for every $x\in\Bbb Q$, thus $f(X) = \det T(X)\in\Bbb Z[X]$.
Best Answer
By the structure theorem of finitely generated modules over principal ideal domains, we can write
$$M \cong F[x]/(e_1) \oplus F[x]/(e_2) \oplus \dotsb \oplus F[x]/(e_s)$$
with $e_1 | e_2 | \dotsc | e_s$.
In particular we have $e_sM=0$, which means the minimal polynomial $m$ is a divisor of $e_s$ and actually one has $m=e_s$. This yields
$$\dim_F M = \deg e_1 + \dotsb + \deg e_s \geq \deg e_s = \deg m.$$
The minimal polynomial and the characteristic polynomial coincide if and only if equality holds, which is the case if and only if $s=1$, which means that $M \cong F[x]/(e_1)$ is cyclic.