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\|_{op}^2\cdot\sum_i\sigma_i(A \circ B)\\
&\le \|A\|_{op}^2\cdot \sum_i \min(r_i(A),c_i(A))\sigma_i(B)\\
&\le \|A\|_{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\|_{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 concentratio, OR
- ...

In case of the first condition, we would use the Chebychev inequality.

  [1]: https://epubs.siam.org/doi/abs/10.1137/S0895479896309645?journalCode=sjmael