It took me some time, but I hope it still helps. Coming back to your problem I realized that the norm constraint is not convex (you should have the opposite inequality for convexity).

Assuming you have the opposite inequality, $ Tr(XA^{\prime})+\|vec(X)^HA\|\leq a$, you can write the problem in standard form:

\begin{eqnarray*}
\min & Tr(XA)+t \\
\mbox{s.t.} & Tr(X A^{\prime})+t+s &= a \\
            & vec(X)^HA^{\prime\prime} &= z \\
            & s &\geq 0 \\
            & (z,t)&\in L^{M+1}\\
            & X &\succeq 0
\end{eqnarray*}

where $L^{M+1}$ is the Lorentz cone in $M+1$ variables. The nice thing about barrier functions is that they (and their complexity) are additive (see http://www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf, page 276), so the complexity of interior point methods would be the sum of the barrier parameter of the positive real line + the barrie parameter of the PSD cone + the barrier parameter of the Lorentz cone (and the square root of that parameter is what comes in the running time of the IPM).

Of course, all this provided you have a convex program.