This should be a comment but I haven't got enough rep, sorry. I don't know how you want to apply the result. So, I'm wondering whether a linear polynomial whose coefficients are $m\times n$ and $n \times m$ matrices would be sufficient for your application. This can be easily achieved by using elementary matrices in order to extract $X$'s entries.
EDIT for elaboration
Let $E_{ij}=E_{ij}^{(n)}$ denote the $n\times n$ matrix that has got zero entries everywhere except for the i-th row and j-th column, i.e. $ \left( E_{ij} \right)_{kl}= \delta _{ik} \delta _{jl} $ .
Then $ E_{ii}\cdot X \cdot E_{jj} $ equals $x_{ij}E_{ij}$.
Well, the embedding $$\iota\colon M(n,R) \to M(m,R) \quad ; \quad M \mapsto \begin{pmatrix} M & 0 \\ 0 & 0 \end{pmatrix}$$ can be described by the matrix $J=(I_n \ 0_{m-n})$, i.e. $\iota(M)=J^t\cdot M\cdot J$.
Let me just steal the next definition from wikipedia http://en.wikipedia.org/wiki/Elementary_matrices
$$T_{i,j} = \begin{bmatrix} 1 & & & & & & & \\ & \ddots & & & & & & \\ & & 0 & & 1 & & \\ & & & \ddots & & & & \\ & & 1 & & 0 & & \\ & & & & & & \ddots & \\ & & & & & & & 1\end{bmatrix}$$
So $T_{ij}\cdot A$ is the matrix produced by exchanging row $i$ and row $j$ of $A$.
Suppose $ y_{kl} = \sum_{ij} z_{kl}^{ij} \cdot x_{ij} $ where $z_{kl}^{ij}$ lies in $\mathbb Z$ then
$$Y=\sum_{ijkl} z_{kl}^{ij} \cdot T_{ik}^{(m)} \cdot J^t \cdot E_{ii}^{(n)} \cdot X \cdot E_{jj}^{(n)} \cdot J \cdot T_{jl}^{(m)} . $$
Or, as I just realized we can permute
$$Y=\sum_{ijkl} z_{kl}^{ij} \cdot T_{ik}^{(m)} \cdot E_{ii}^{(m)}\cdot J^t\cdot X\cdot J \cdot E_{jj}^{(m)} \cdot T_{jl}^{(m)} . $$
But both formulas give the exact same shortened version
$$ Y = \sum_{ijkl} A_{kl}^{ij} \cdot X \cdot B_{l}^{ij} $$
where $B_{kl}^{ij}$ is independent of $k$.
