You are correct: any matrix can be a cross-covariance matrix. But it doesn't look straightforward to prove. Here is an outline of a proof and an effective algorithm for finding the random variables $X$ and $Y$.
Let $B$ be an $m\times n$ real matrix (which could be any of the $\Sigma_i$ in the question). Replacing $B$ with its transpose $B^\prime$ if necessary, we may assume without any loss of generality that $m \le n.$
First, find an $m\times m$ invertible matrix $S$ and an $n\times n$ invertible matrix $T$ for which $S\,B\,T$ is diagonal. This is the Smith normal form of $B.$ It can be found by row-reducing and then column-reducing $B.$ Because the coefficients of $B$ are in a field, we may take the first $r$ diagonal elements of $SBT$ to be unity and the remaining ones to be zero, where of course $0\le r \le m.$ In block-matrix notation this means
$$S\,B\,T = \left(\begin{array}{c|c} \mathbb{I}_r & \mathbb{O}_{r\times n-r}\\ \hline \mathbb{O}_{m-r\times r} & \mathbb{O}_{m-r\times n-r}\end{array}\right)$$
The $\mathbb{I}$ matrix is the $r\times r$ identity and all the $\mathbb{O}$ matrices are zero-matrices; subscripts denote the dimensions.
This (by inspection) could be the off-diagonal block of an $m+n\times m+n$ covariance matrix provided there are $r$ pairs of perfectly correlated variables. In light of this, consider the $m\times m$ matrix $A$ with
$$A = \left(\begin{array}{c|c} \mathbf{1}_r\,\mathbf{1}_r^\prime & \mathbb{O}_{r\times m-r}\\ \hline \mathbb{O}_{m-r\times r} & \mathbb{I}_{m-r\times m-r}\end{array}\right)$$
and the $n\times n$ matrix $\Delta$ with
$$\Delta = \left(\begin{array}{c|c} \mathbf{1}_r\,\mathbf{1}_r^\prime & \mathbb{O}_{r\times n-r}\\ \hline \mathbb{O}_{n-r\times r} & \mathbb{I}_{n-r\times n-r}\end{array}\right)$$
Here, $\mathbf{1}_r$ is the column $r$-vector of ones.
From these three ingredients form the $m+n\times m+n$ matrix
$$\Upsilon = \left(\begin{array}{c|c} A & S\,B\,T\\ \hline T^\prime B^\prime S^\prime & \Delta\end{array}\right)
= \left(\begin{array}{c|c} \begin{array}{c|c} \mathbf{1}_r\,\mathbf{1}_r^\prime & \mathbb{O}_{r\times m-r}\\
\hline \mathbb{O}_{m-r\times r} & \mathbb{I}_{m-r\times m-r}\end{array} & \begin{array}{c|c} \mathbb{I}_r & \mathbb{O}_{r\times n-r}\\
\hline \mathbb{O}_{m-r\times r} & \mathbb{O}_{m-r\times n-r}\end{array}\\
\hline \begin{array}{c|c} \mathbb{I}_r & \mathbb{O}_{r\times m-r}\\
\hline \mathbb{O}_{n-r\times r} & \mathbb{O}_{n-r\times m-r}\end{array} & \begin{array}{c|c} \mathbf{1}_r\,\mathbf{1}_r^\prime & \mathbb{O}_{r\times n-r}\\
\hline \mathbb{O}_{n-r\times r} & \mathbb{I}_{n-r\times n-r}\end{array}\end{array}\right)$$
This matrix $\Upsilon$ is positive semi-definite (and therefore is a covariance matrix). To see this, permute the rows and columns to put the two blocks of ones in the upper left, producing the equivalent matrix
$$\Upsilon_0 = \left(\begin{array}{c|c|c} \mathbf{1}_r\,\mathbf{1}_r^\prime & \mathbb{O}_{r\times r}& \mathbb{O}_{r\times m+n-2r}\\
\hline \mathbb{O}_{r\times r} & \mathbf{1}_r\,\mathbf{1}_r^\prime & \mathbb{O}_{r\times m+n-2r}\\
\hline \mathbb{O}_{m+n-2r \times r} & \mathbb{O}_{m+n-2r\times r} & \mathbb{I}_{m+n-2r}\end{array}\right)$$
Writing an arbitrary $m+n$-row vector as $\mathbf{x}=(x_r, y_r, z_{m+n-2r})$ in terms of two $r$-vectors and an $m+n-2r$ vector, compute
$$\mathbf{x}\,\Upsilon_0\,\mathbf{x}^\prime = (x_r\mathbf{1}_r)^2 + (y_r\mathbf{1}_r)^2 + z_{m+n-2r}\,z_{m+n-2r}^\prime \ge 0,\tag{*}$$
showing $\Upsilon_0$ is positive semi-definite (this is the definition) and therefore $\Upsilon$ is positive semi-definite.
We may, however, write
$$\Upsilon = \left(\begin{array}{c|c} S & \mathbb{O}_{m\times n}\\ \hline \mathbb{O}_{n\times m} & T^\prime\end{array}\right)
\ \left(\begin{array}{c|c} S^{-1}A (S^\prime)^{-1} & B\\ \hline B^\prime & (T^\prime)^{-1} \Delta T^{-1}\end{array}\right)
\ \left(\begin{array}{c|c} S^\prime & \mathbb{O}_{m\times n}\\ \hline \mathbb{O}_{n\times m} & T\end{array}\right).$$
Name those three $m+n\times m+n$ matrices at the right $U,$ $\Sigma,$ and $U^\prime,$ respectively. Recalling that $S$ and $T$ are invertible it follows $U$ is invertible, whence
$$\Sigma = U^{-1}\,\Upsilon\,(U^\prime)^{-1}.$$
Now $\Sigma$ is obviously positive semidefinite, because for any $m+n$ row vector $\mathbf{x},$
$$\mathbf{x}\,\Sigma\,\mathbf{x}^\prime = (\mathbf{x} U^{-1})\, \Upsilon\, (\mathbf{x}U^{-1})^\prime \ge 0$$
by virtue of $(*).$
$\Sigma$ solves the problem: it is a covariance matrix in which $B$ is the cross-covariance between the first $m$ and last $n$ variables.
In particular, let $X$ be the $m$-variate random variable and $Y$ the $n$-variate random variable. Their variances and cross-covariance are
$$\operatorname{Var}(X) = S^{-1}A(S^\prime)^{-1};\quad \operatorname{Var}(Y) = (T^\prime)^{-1}\Delta T^{-1};\quad \operatorname{Cov}(X,Y) = B.$$
Example
Consider $$B=\Sigma_5 = \pmatrix{0&1&0 \\ 0&1&0 \\ 0&1&0}.$$ Row-reduction produces $S$ and then column-reduction of the result produces $T$ with
$$S=\pmatrix{1&0&0 \\ -1&1&0 \\ -1&0&1},\quad T=\pmatrix{0&1&0 \\ 1&0&0 \\ 0&0&1}$$
and $r=1.$ Therefore $A = \Delta = \mathbb{I}_3$ and
$$S^{-1}A(S^\prime)^{-1} = \pmatrix{1&1&1 \\ 1&2&1 \\ 1&1&2};\quad T^{-1}\Delta(T^\prime)^{-1} = \mathbb{I}_3.$$
Consequently
$$\Sigma= \pmatrix{1&1&1 &0&1&0 \\
1&2&1 &0&1&0 \\
1&1&2 &0&1&0 \\
0&0&0 &1&0&0 \\
1&1&1 &0&1&0 \\
0&0&0 &0&0&1}.$$
You can check (by computing eigenvalues, for instance) that this matrix is positive semi-definite and you can see that $B$ is the cross-covariance of the first three and last three variables. Finally, the non-trivial upper $3\times 3$ matrix indicates there isn't any magical way to simplify the results of this analysis (as one might initially hope).
