As Gro-Tsen pointed out, I had not computed the Galois group of the governing polynomial, and, in fact, my original answer was wrong. I believe that the following answer is correct, though.

If by 'like the above form' you mean an expression in terms of radicals of the traces of the powers of $M$, the answer is 'no' for $n>5$. Even for $n=3$ and $n=4$, when there is such an expression, it is very ugly and will almost certainly be useless for any practical purpose:

Let $p_i = \mathrm{tr}(M^i)$ for $1\le i\le n$, and let $q = \|A\|_*$. If $\lambda_1,\ldots,\lambda_n\ge 0$ are the eigenvalues of $M$, then $p_i = {\lambda_1}^i+\cdots+{\lambda_n}^i$ and $q = \sqrt{\lambda_1}+\cdots+\sqrt{\lambda_n}$. The problem is to compute the Galois group of the minimal polynomial of $q$ in the field generated by the $p_i$ and determine whether it is solvable, since this will determine whether $q$ can be expressed algebraically in terms of the $p_i$ using only radicals.

To clarify things, write $\mu_i = \sqrt{\lambda_i}$, so that $q = \mu_1 + \cdots + \mu_n$ while $p_i = {\mu_1}^{2i}+\cdots+{\mu_n}^{2i}$.

Let $\mathbb{S}_n\subset\mathrm{O}(n)$ be the signed permutation group acting linearly on the span of the $\mu_i$. Thus, $\sigma\in \mathbb{S}_n$ satisfies $\sigma(\mu_i) = \epsilon_i\,\mu_{\pi(i)}$ where $\epsilon_i=\pm1$ and $\pi$ is a permutation of $\{1,\ldots,n\}$. Then $\sigma$ extends to an automorphism of the field $\mathbb{Q}(\mu_1,\ldots,\mu_n)$ whose fixed field is easily seen to be $\mathbb{Q}(p_1,\ldots,p_n)$. Let $(\mathbb{Z}_2)^n\subset\mathbb{S}_n$ be the abelian normal subgroup consisting of the $\sigma$ of the form $\sigma(\mu_i) = \epsilon_i\,\mu_{i}$ where $\epsilon_i=\pm1$.

Consider the polynomial $$ f(t) = \prod_{\sigma\in(\mathbb{Z}_2)^n}\bigl(t-\sigma(q)\bigr). $$ Then $f(q) = 0$. The $t$-degree of $f$ is $2^n$, and it is easy to see that the $t$-coefficients of $f$ lie in $\mathbb{Q}(p_1,\ldots,p_n)$ (since they are symmetric polynomials in ${\mu_1}^2,\ldots,{\mu_n}^2$). Moreover, the set $R=\{\sigma(q)\ |\ \sigma\in (\mathbb{Z}_2)^n\}$ consists of $2^n$ distinct elements, which are the roots of $f$ in $\mathbb{Q}(\mu_1,\ldots,\mu_n)$. The group $\mathbb{S}_n$ acts transitively on $R$, and the $\mathbb{Q}$-linear span of $R$ contains $\mu_1,\ldots,\mu_n$, so $\mathbb{Q}(\mu_1,\ldots,\mu_n)$ is the splitting field of $f$. (Hence $f$ must be irreducible.)

If $\alpha$ is an automorphism of $\mathbb{Q}(\mu_1,\ldots,\mu_n)$ that preserves the set $R$, then it must preserve its $\mathrm{Q}$-linear span and it must preserve the sum of the squares of the elements of $R$, which is clearly $2^n({\mu_1}^2 + \cdots + {\mu_n}^2)$. From this, it is easy to see that $\alpha$ must preserve the set $\{\pm\mu_1,\ldots,\pm\mu_n\}$ and hence must belong to $\mathbb{S}_n$. Thus, the Galois group of $f$ is $\mathbb{S}_n$.

Since $\mathbb{S}_n/(\mathbb{Z}_2)^n$ is isomorphic to the permutation group $S_n$ and since $(\mathbb{Z}_2)^n$ is abelian, it follows that $\mathbb{S}_n$ is solvable if and only if $S_n$ is solvable. Of course, $S_n$ is solvable if and only if $n<5$.

As Gro-Tsen pointed out, I had not computed the Galois group of the governing polynomial, and, in fact, my original answer was wrong. I believe that the following answer is correct, though.

If by 'like the above form' you mean an expression in terms of radicals of the traces of the powers of $M$, the answer is 'no' for $n>5$. Even for $n=3$ and $n=4$, when there is such an expression, it is very ugly and will almost certainly be useless for any practical purpose:

Let $p_i = \mathrm{tr}(M^i)$ for $1\le i\le n$, and let $q = \|A\|_*$. If $\lambda_1,\ldots,\lambda_n\ge 0$ are the eigenvalues of $M$, then $p_i = {\lambda_1}^i+\cdots+{\lambda_n}^i$ and $q = \sqrt{\lambda_1}+\cdots+\sqrt{\lambda_n}$. The problem is to compute the Galois group of the minimal polynomial of $q$ in the field generated by the $p_i$ and determine whether it is solvable, since this will determine whether $q$ can be expressed algebraically in terms of the $p_i$ using only radicals.

To clarify things, write $\mu_i = \sqrt{\lambda_i}$, so that $q = \mu_1 + \cdots + \mu_n$ while $p_i = {\mu_1}^{2i}+\cdots+{\mu_n}^{2i}$.

Let $\mathbb{S}_n\subset\mathrm{O}(n)$ be the signed permutation group acting linearly on the span of the $\mu_i$. Thus, $\sigma\in \mathbb{S}_n$ satisfies $\sigma(\mu_i) = \epsilon_i\,\mu_{\pi(i)}$ where $\epsilon_i=\pm1$ and $\pi$ is a permutation of $\{1,\ldots,n\}$. Then $\sigma$ extends to an automorphism of the field $\mathbb{Q}(\mu_1,\ldots,\mu_n)$ whose fixed field is easily seen to be $\mathbb{Q}(p_1,\ldots,p_n)$. Let $(\mathbb{Z}_2)^n\subset\mathbb{S}_n$ be the abelian normal subgroup consisting of the $\sigma$ of the form $\sigma(\mu_i) = \epsilon_i\,\mu_{i}$ where $\epsilon_i=\pm1$.

Consider the polynomial $$ f(t) = \prod_{\sigma\in(\mathbb{Z}_2)^n}\bigl(t-\sigma(q)\bigr). $$ Then $f(q) = 0$. The $t$-degree of $f$ is $2^n$, and it is easy to see that the $t$-coefficients of $f$ lie in $\mathbb{Q}(p_1,\ldots,p_n)$ (since they are symmetric polynomials in ${\mu_1}^2,\ldots,{\mu_n}^2$). Moreover, the set $R=\{\sigma(q)\ |\ \sigma\in (\mathbb{Z}_2)^n\}$ consists of $2^n$ distinct elements, which are the roots of $f$ in $\mathbb{Q}(\mu_1,\ldots,\mu_n)$. The group $\mathbb{S}_n$ acts transitively on $R$, and the $\mathbb{Q}$-linear span of $R$ contains $\mu_1,\ldots,\mu_n$, so $\mathbb{Q}(\mu_1,\ldots,\mu_n)$ is the splitting field of $f$. (Hence $f$ must be irreducible in $\mathbb{Q}(p_1,\ldots,p_n)[t]$.)

If $\alpha$ is an automorphism of $\mathbb{Q}(\mu_1,\ldots,\mu_n)$ that preserves the set $R$, then it must preserve its $\mathrm{Q}$-linear span and it must preserve the sum of the squares of the elements of $R$, which is clearly $2^n({\mu_1}^2 + \cdots + {\mu_n}^2)$. From this, it is easy to see that $\alpha$ must preserve the set $\{\pm\mu_1,\ldots,\pm\mu_n\}$ and hence must belong to $\mathbb{S}_n$. Thus, the Galois group of $f$ is $\mathbb{S}_n$.

Since $\mathbb{S}_n/(\mathbb{Z}_2)^n$ is isomorphic to the permutation group $S_n$ and since $(\mathbb{Z}_2)^n$ is abelian, it follows that $\mathbb{S}_n$ is solvable if and only if $S_n$ is solvable. Of course, $S_n$ is solvable if and only if $n<5$.

If by 'like the above form' you mean an expression in terms of radicals of the traces of the powers of $M$, the answer is 'no' for $n>3$. Even for $n=3$, where there is such an expression, it is very ugly and will almost certainly be useless for any practical purpose:

In the case $n=3$, let $p_i = \mathrm{tr}(M^i)$ for $i=1,2,3$, and let $q = \bigl(\|A\|_*\bigr)^2$. Then the relation between $p_1$, $p_2$, $p_3$, and $q$ is found to be $$ 0 = q^4 - 4p_1\,q^3 + (4p_2{+}2p_1^2)\,q^2 + (24p_1p_2{-}{\tfrac{20}{3}}p_1^3{-}{\tfrac{64}{3}}p_3)\,q + (p_1^4{-}4p_1^2p_2{+}4p_2^2), $$ so one can solve for $q$ in radicals using the quartic equation and then take the square root to get $\|A\|_*$. That's the 'simplest' explicit analytical expression.

For higher $n$, there will still be such a polynomial, but of higher degree in $q$, and there won't be a solution in radicals.

As Gro-Tsen pointed out, I had not computed the Galois group of the governing polynomial, and, in fact, my original answer was wrong. I believe that the following answer is correct, though.

If by 'like the above form' you mean an expression in terms of radicals of the traces of the powers of $M$, the answer is 'no' for $n>5$. Even for $n=3$ and $n=4$, when there is such an expression, it is very ugly and will almost certainly be useless for any practical purpose:

Let $p_i = \mathrm{tr}(M^i)$ for $1\le i\le n$, and let $q = \|A\|_*$. If $\lambda_1,\ldots,\lambda_n\ge 0$ are the eigenvalues of $M$, then $p_i = {\lambda_1}^i+\cdots+{\lambda_n}^i$ and $q = \sqrt{\lambda_1}+\cdots+\sqrt{\lambda_n}$. The problem is to compute the Galois group of the minimal polynomial of $q$ in the field generated by the $p_i$ and determine whether it is solvable, since this will determine whether $q$ can be expressed algebraically in terms of the $p_i$ using only radicals.

To clarify things, write $\mu_i = \sqrt{\lambda_i}$, so that $q = \mu_1 + \cdots + \mu_n$ while $p_i = {\mu_1}^{2i}+\cdots+{\mu_n}^{2i}$.

Let $\mathbb{S}_n\subset\mathrm{O}(n)$ be the signed permutation group acting linearly on the span of the $\mu_i$. Thus, $\sigma\in \mathbb{S}_n$ satisfies $\sigma(\mu_i) = \epsilon_i\,\mu_{\pi(i)}$ where $\epsilon_i=\pm1$ and $\pi$ is a permutation of $\{1,\ldots,n\}$. Then $\sigma$ extends to an automorphism of the field $\mathbb{Q}(\mu_1,\ldots,\mu_n)$ whose fixed field is easily seen to be $\mathbb{Q}(p_1,\ldots,p_n)$. Let $(\mathbb{Z}_2)^n\subset\mathbb{S}_n$ be the abelian normal subgroup consisting of the $\sigma$ of the form $\sigma(\mu_i) = \epsilon_i\,\mu_{i}$ where $\epsilon_i=\pm1$.

Consider the polynomial $$ f(t) = \prod_{\sigma\in(\mathbb{Z}_2)^n}\bigl(t-\sigma(q)\bigr). $$ Then $f(q) = 0$. The $t$-degree of $f$ is $2^n$, and it is easy to see that the $t$-coefficients of $f$ lie in $\mathbb{Q}(p_1,\ldots,p_n)$ (since they are symmetric polynomials in ${\mu_1}^2,\ldots,{\mu_n}^2$). Moreover, the set $R=\{\sigma(q)\ |\ \sigma\in (\mathbb{Z}_2)^n\}$ consists of $2^n$ distinct elements, which are the roots of $f$ in $\mathbb{Q}(\mu_1,\ldots,\mu_n)$. The group $\mathbb{S}_n$ acts transitively on $R$, and the $\mathbb{Q}$-linear span of $R$ contains $\mu_1,\ldots,\mu_n$, so $\mathbb{Q}(\mu_1,\ldots,\mu_n)$ is the splitting field of $f$. (Hence $f$ must be irreducible.)

If $\alpha$ is an automorphism of $\mathbb{Q}(\mu_1,\ldots,\mu_n)$ that preserves the set $R$, then it must preserve its $\mathrm{Q}$-linear span and it must preserve the sum of the squares of the elements of $R$, which is clearly $2^n({\mu_1}^2 + \cdots + {\mu_n}^2)$. From this, it is easy to see that $\alpha$ must preserve the set $\{\pm\mu_1,\ldots,\pm\mu_n\}$ and hence must belong to $\mathbb{S}_n$. Thus, the Galois group of $f$ is $\mathbb{S}_n$.

Since $\mathbb{S}_n/(\mathbb{Z}_2)^n$ is isomorphic to the permutation group $S_n$ and since $(\mathbb{Z}_2)^n$ is abelian, it follows that $\mathbb{S}_n$ is solvable if and only if $S_n$ is solvable. Of course, $S_n$ is solvable if and only if $n<5$.