As a first step towards a solution, I computed this integral for the trace,
$$\int_{\mathcal{U}(N)}{\rm tr}\, (AUA^\dagger U^\dagger)\,\overline{{\rm tr}\,(AUA^\dagger U^\dagger)}\,dU=\frac{1}{N^2-1}\left(|{\rm tr}\, A|^4+|{\rm tr}\,AA^\dagger|^2\right)-\frac{2}{N(N^2-1)}\left(|{\rm tr}\,A|^2+{\rm tr}\,AA^\dagger\right).$$