Let $K$ be an arbitrary field and let $A\in\mathbb{M}_n(K)$. Let $m(X)$ and $p(X)$ be the minimal polynomial of $A$ over $K$ and the characteristic polynomial of $A$ over $K$, respectively.
According to the Wikipedia article about companion matrix, the following are equivalent:
$~~\deg(m(X))=\deg(p(X))=n$.
$~~A=S^{-1}C_pS~~$ for some invertible matrix $S\in\mathbb{M}_n(K)$, where $C_p$ is the companion matrix over $K$ of $p(X)$.
I can show that (2) implies (1). But I do not know how to prove the other direction. If $K$ is an infinite filed or $m(X)$ is irreducible over $K$, I can prove that (1) implies (2). But I cannot in general.
One idea is to carefully extend whatever proof would work over a sufficiently "nice" field. For instance: if we consider $A$ as a matrix over $\bar K$, the algebraic closure of $K$, then we can now apply Jordan canonical form. Because the exponents of the linear terms in the minimal polynomial are the sizes of the largest blocks associated with an eigenvalue, we can determine that if $A$ satisfies (1), then its Jordan form has exactly one block per eigenvalue. This is enough for us to conclude that any to matrices satisfying (1) are similar over $\bar K$. So, there is a matrix $S$ with entries in $\bar K$ such that $$ A = S^{-1}C_pS $$ From there, we would need a lemma to the effect that matrices $A$ and $B$ are matrices in $K$ that are similar over $\bar K$, then those matrices must also be similar over $K$.
For a more direct proof, we could use the structure theorem over finitely generated PIDs. Applied to this context, the theorem tells us that every matrix $A$ has a rational canonical form. That is, every $A$ satisfies $A = S^{-1}CS$ where $C$ is a diagonal direct sum of companion matrices. One good reference for a proof would be Dummit and Foote. A more linear-algebra specific reference is Hoffman and Kunze, which presents rational canonical form in chapter 7.
Once you understand rational canonical form, this problem is an easy exercise. Note in particular that the minimal polynomial of $C_{p_1} \oplus \cdots \oplus C_{p_k}$ will be the least common multiple of the polynomials $p_j$.