is $+$ actually the "Hermitian" conjugate instead of the complex conjugate? Is $U^{\otimes m }$ randomly taken from $U(d^m)$ or it's just a $u\otimes u \otimes u \cdots u$ where $u$ is randomly taken from $U(d)$. I don't understand the measure of the integral, because $U^{\otimes m}$ and $U^{\otimes m+k}$ live in $U(d^m)$ and $U( d^{m+k} )$ with different Haar measure. Please edit to clarify especially the dimensions of those matrices and which unitary group you take the Haar measure.

The Weingarten function may be helpful in evaluating the Haar integral. See this MO post and relevant wikipedia articles.

Thanks for providing the reference. Lemma 1 gives the optimal way of increasing cycles. Excellent proof!