Let $k \le n$ be the rank of $B$, and for $1 \le i \le k$, let $r_i(A)$ be the euclidean norm of the $i$th row of $A$ and let $c_i(A)$ be the Euclidean norm of the $i$th column of $A$. Taking things from where the OP left off, one can write $$ \begin{split} \left|\mbox{tr}(A^2 (A \circ B))\right| &\le \sum_i \sigma_i(A)^2 \sigma_i(A \circ B) \le \|A\|_{\mathrm{op}}^2\cdot\sum_i\sigma_i(A \circ B)\\ &\le \|A\|_{\mathrm{op}}^2\cdot \sum_i \min(r_i(A),c_i(A))\sigma_i(B)\\ &\le \|A\|_{\mathrm{op}}^2\|B\|_\star\cdot\max_{1 \le i \le k}\min(r_i(A),c_i(A)), \end{split} $$ where $\|B\|_\star := \sum_i \sigma_i(B)$ is the nuclear norm of $B$ and the second line is by **Theorem 1** of ["INEQUALITIES FOR THE SINGULAR VALUES OF HADAMARD PRODUCTS"][1]. Now, by standard RMT, we know that $\|A\|_{\mathrm{op}} = \mathcal O(1)$ with probability $1-e^{-cn}$. Also, other certain conditions (see further below), each $r_i(A)^2$, and therefore each $c_i(A)^2$, verifies $|r_i(A)^2-1| \le t$ w.p $1-c/k^{1+\delta}$, for some universal $\delta > 0$. Putting things togethe, we deduce via a simple union bound that >$\left|\mbox{tr}(A^2(A \circ B))\right| \lesssim \|B\|_\star$ with arbitrarily high probability. --- For the concentration of the $r_i(A)^2$, any of the following conditions is sufficient - $k = o(n)$ (or roughly said, $k/n \to \infty$), OR - $A_{ij}$ has sub-Gaussian concentration, OR - ... In case of the first condition, we would use the Chebyshev inequality. [1]: https://epubs.siam.org/doi/abs/10.1137/S0895479896309645?journalCode=sjmael