Deriving the sub-differential of the nuclear norm

Contrary to my first impression, this question is answered completely and thoroughly by G.A. Watson in Characterization of the Subdifferential of Some Matrix Norms. For the final derivation, see pg. 40.

The conclusion is that

$$\partial \|K\|_* = \left\{ UV^T+W:\ \ \ \|W\|<1, \text{columnspace}(U) \perp W\perp\text{ rowspace(V)} \right\},$$

where $\|\cdot\|$ is the spectral norm, which is dual to the nuclear norm.

This is rather a comment, but a little bit longer.

There is a nice characterization of the subdifferentials of norms: If $X$ is a normed space, we have $$ \partial \|\cdot\| (x) = \{ x^* \in X^* : \|x^*\|_{X^*} \le 1 \text{ and } \langle x^*, x\rangle = \|x\|_X\}, $$ where $X^*$ is the topological dual of $X$ (and $\|\cdot\|_{X^*}$ is the dual norm).

I can't find a reference about the dual of your nuclear norm, but maybe this comment helps.