$$ \underset{A,x}{\text{minimize}} \quad \lambda \left\| x \right\|_{1} + \left\| A \right\|_{*} $$
$$ D = A + Mx $$
Where $M \in \mathbb{R}^{n \times m}$, $x \in \mathbb{R}^{m \times z}$, $E=Mx \in \mathbb{R}^{n \times z}$, $n<<m$, $A \in \mathbb{R}^{n \times z}$ and $D \in \mathbb{R}^{n \times z}$
Yes, you could solve this using some proximal algorithm such as the Douglas-Rachford method.
Let $C = \{ (A,x) \mid D = A + Mx \}$, and let $I_C$ be the indicator function of $C$: \begin{equation} I_C(A,x) = \begin{cases} 0 & \text{if } D = A + Mx, \\ \infty & \text{otherwise.} \end{cases} \end{equation} Your problem can be restated as \begin{equation} \text{minimize} \quad \underbrace{\lambda \|x\|_1 + \|A\|_*}_{f(A,x)} + \underbrace{I_C(A,x)}_{g(A,x)}. \end{equation} You can use the Douglas-Rachford method to minimize $f + g$. At each iteration, you will have to evaluate the proximal operators of $f$ and $g$. Evaluating the prox-operator of $f$ reduces to separately evaluating the prox-operators of the $L_1$ norm and the spectral norm. The prox-operator of $g$ projects onto $C$, which is a linear algebra problem.
Two good sources to learn about proximal algorithms are the book Proximal Algorithms by Boyd and Parikh, and Vandenberghe's 236c notes.