After a cyclic permutation of the trace, the expression you need is

$$Y=\text{tr}\left\{\mathbf{A}^HE(\mathbf{C}^H \begin{bmatrix} \mathbf{0}_{M\times M} & \mathbf{0}_{M\times N} \\ \mathbf{0}_{N\times M} & \mathbf{I}_{N\times N} \end{bmatrix} \mathbf{C})\mathbf{A}\right\}=\text{tr}\left\{E(\mathbf{C}\mathbf{A}\mathbf{A}^H \mathbf{C}^H) \begin{bmatrix} \mathbf{0}_{M\times M} & \mathbf{0}_{M\times N} \\ \mathbf{0}_{N\times M} & \mathbf{I}_{N\times N} \end{bmatrix} \right\}$$

Let me abbreviate $\mathbf{H}=\mathbf{AA}^H$, $\mathbf{X}=\mathbf{C}\mathbf{A}\mathbf{A}^H \mathbf{C}^H$, and let me denote by $\mathbf{P}$ the projection matrix in square brackets, so $Y={\rm tr}\{E(\mathbf{X})\mathbf{P}\}$. The expectation value can be evaluated using the Toeplitz property $C_{ij}=c_{i-j}$. I denote $E(c_i c^\ast_j)=\tfrac{1}{2}\sigma_i^2\delta_{ij}$.

$$E(X_{ij})=\sum_{kl}E(C_{ik}H_{kl}C^\ast_{jl})=\sum_{kl}E(c_{i-k}H_{kl}c^\ast_{j-l})=\tfrac{1}{2}\sum_{kl}\sigma^2_{i-k}H_{kl}\delta_{i-k,j-l}=\tfrac{1}{2}\sum_{k}\sigma^2_{i-k}H_{k,k+j-i}$$
In the last sum over $k$ only terms with $1\leq k+j-i\leq N+M$ are to be retained.

The projector $\mathbf{P}$ identifies $j=i=M+1,M+2,\ldots M+N$, so we arrive at

$$Y={\rm tr}\{E\mathbf{(X)P}\}=\tfrac{1}{2} \sum_{i=M+1}^{N+M}\sum_{k=1}^{N+M}\sigma^2_{i-k}H_{kk}$$

If your Toeplitz matrix would be full, I would just replace $\sigma^2_{i-k}\mapsto\sigma^2$ and arrive at $Y=\tfrac{1}{2}\sigma^2 N\,{\rm tr}\,\mathbf{AA}^H$. The construction you have has all these zero entries, so this will modify the answer. I am not quite sure I understand your construction, which elements you equate to zero and which not, but hopefully you can take it from here.