The companion matrices of $x^2-m$ and $x^2-n$ are: $$ \left(\begin{array}{cc} 0&m\\ 1&0 \end{array}\right) \quad\mbox{and}\quad \left(\begin{array}{cc} 0&n\\ 1&0 \end{array}\right)~. $$ Thus $A\otimes1+1\otimes B$ is given by $$ \left(\begin{array}{cccc} 0&0&m&0\\ 0&0&0&m\\ 1&0&0&0\\ 0&1&0&0 \end{array}\right) +\left(\begin{array}{cccc} 0&n&0&0\\ 1&0 &0&0\\ 0&0&0&n\\ 0&0&1&0 \end{array}\right) =\left(\begin{array}{cccc} 0&n&m&0\\ 1&0&0&m\\ 1&0&0&n\\ 0&1&1&0 \end{array}\right) $$ and its characteristic polynomial is $z^4-2(m+n)z^2+(m-n)^2=0$.
Remark: The roots of the latter polynomial are $\pm\sqrt m\pm\sqrt n$, which are just all possible sums of the roots of the first and the second polynomial. Thus another way to find a polynomial $r\in\Z[X]$ with root $a_1+b_1$ is indeed the following: if $a_1,\ldots,a_m\in\C$ are all the roots of $p\in\Z[X]$ and $b_1,\ldots,b_n$ all the roots of $q\in\Z[X]$, then $$ r\colon=\prod_{j=1}^m\prod_{k=1}^n(X-a_j-b_k) $$ is a monic polynomial in $\Z[X]$, because it's the characteristic polynomial of $A\otimes1+1\otimes B$. However, there is a catch in it: you need to know all the roots of $p$ and $q$.