First, I'll note that the statement given is incorrect, read literally. For one thing, you need $q(x)$ to be monic, since the minimal polynomial is always monic; also, depending on your definition of characteristic polynomial, you need either $p(x)$ to be monic, or you need the leading coefficient to be $(-1)^{\deg p}$.
Even with those to issues, it is still incorrect as written:
Take $k=\mathbb{R}$, $p(x) = x^4-1$, and $q(x)=x^2-1$. Since $p(x)=(x^2-1)(x^2+1)$, then $q(x)$ divides $p(x)$. In addition, every root of $p(x)$ is a root of $q(x)$ (the only roots are $1$ and $-1$. However, there is no matrix that has $x^4-1$ as the characteristic polynomial and $x^2-1$ as the minimal polynomial (even over $\mathbb{C}$). Why? Because every irreducible factor of the characteristic polynomial of $A$ must divide the minimal polynomial of $A$. So if a matrix with real coefficients has characteristic polynomial $x^4-1$, then the minimal polynomial must be a multiple of $x^2+1$, which $q(x)$ is not.
To fix the statement, you should change
... every root of $p(x)$ is a root of $q(x)$ ...
to
... every root of $p(x)$ in an algebraic closure of $k$ is a root of $q(x)$...
Once that change is made, the asserted result is true.
The simplest way to do this is to use the Rational Canonical Form. Let $\phi_1(x),\ldots,\phi_k(x)$ be the irreducible factors (over $k$) of $p(x)$: $p(x) = (-1)^{n}(\phi_1(x))^{n_1}\cdots (\phi_k(x))^{n_k}.$ The conditions on $q(x)$ and $p(x)$ mean that $\phi_1,\ldots,\phi_k$ are also precisely the irreducible factors of $q(x)$, so we have $q(x) = (\phi_1(x))^{m_1}\cdots (\phi_k(x))^{m_k}$ where $1\leq m_i\leq n_k$ for each $i$.
This tells you that in the rational canonical form for the matrix you are looking for, the companion matrices corresponding to $\phi_i(x)$ will have a block corresponding to the companion matrix of $\phi_i(x)^{m_i}$, but no companion matrix with larger power; and the exponents will add up appropriately to give the characteristic polynomial. So the simplest way to construct a matrix with $p(x)$ as the characteristic polynomial and $q(x)$ as the minimal polynomial is to take a block diagonal matrix in which each block is a companion matrix, with one block each for $\phi_1(x)^{m_1}$, $\phi_2(x)^{m_2},\ldots,\phi_k(x)^{m_k}$, and then "fill out" with $n_1-m_1$ companion blocks for $\phi_1(x)$, $n_2-m_2$ companion blocks for $\phi_2$, etc. This gives a matrix over $k$ that has $p(x)$ as the characteristic polynomial and $q(x)$ as the minimal polynomial
If $p(x)$ splits over $k$, you can instead use the Jordan canonical form. The multiplicities of the roots in $q(x)$ give you the largest Jordan block size that needs to be and can be present, while the multiplicities in $p(x)$ tell you how many $1\times 1$ blocks you should add to "fill out" the matrix.