Is every solution of this matrix equation diagonal?

There's exceptions, at least in 2 dimensions: if $$ S = \begin{pmatrix} a & b \\ c & d \end{pmatrix} , $$ the equation is equivalent to $$ A = \begin{pmatrix} a - \lambda d/\Delta & b + \lambda c/\Delta \\ c + \lambda b/\Delta & d - \lambda a/\Delta \end{pmatrix} , $$ where $\Delta = ad-bc$. Asking for the off-diagonal entries to be $0$ forces $ c = \pm b $ and $b = \sqrt{ \lambda \pm ad} $, provided that they are not $0$ to start with, and then $\Delta = \pm \lambda $, so either $$ A = (a+d)I \quad \text{or} \quad A = \operatorname{diag}(a-d,-a+d) , $$ and the second is excluded since $\det{A}>0$. This will also extend to $n$ dimensions any time $A$ has two equal eigenvalues, of course. In particular, the second one will be allowed for matrices such as $\operatorname{diag}(\mu,-\mu,-1)$, so for dimensions larger than $2$, both types of solution are possible.

This leaves the general case of nonequal roots. We can improve on sufficiency of $S$ being symmetric to $S$ being (real-)normal:

In general, we have $$ S^T A = S^T S - \lambda I \quad \text{and} \quad AS^T = SS^T - \lambda I , $$ and taking the transpose of the first gives $$ AS = A^T S = S^T S - \lambda I $$ so $S^T-S = A^{-1} [S^T,S] $: if $S$ is normal, it is symmetric.

$ (S^T)^{-1} = \lambda^{-1} (A - S) $, so $ S^T = \lambda (A-S)^{-1} $, and I'm now also stuck.

We consider two possibilities:

1. All diagonal entries of $A=\operatorname{diag}(a_1,\ldots,a_n)$ have different moduli. The equation $$ A=S-\lambda(S^T)^{-1},\tag{1} $$ implies that both $AS^T=SS^T-\lambda I$ and $S^TA=S^TS-\lambda I$. Therefore both $AS^T$ and $S^TA$ are symmetric and \begin{cases} a_is_{ji}=(AS^T)_{ij}=(SA)_{ij}=s_{ij}a_j,\\ s_{ji}a_j=(S^TA)_{ij}=(AS)_{ij}=a_is_{ij}. \end{cases} Since $|a_i|\ne|a_j|$, these two equalities imply that $s_{ij}=s_{ji}=0$. Hence $S$ is diagonal.

2. $A$ has two elements of the same moduli. When $A$ is $2\times2$, by comparing elements on both sides of $(1)$ directly, it can be shown that one of the following two cases must be true:

   • $S=\pmatrix{a&b\\ b&d},\ \lambda=-\det(S)$ and $A=(a+d)I$, or
   • $S=\pmatrix{a&-b\\ b&d},\ \lambda=\det(S)$ and $A=\pmatrix{a-d&0\\ 0&d-a}$.

   It follows that in the original problem, $S$ is not always diagonal. E.g. \begin{aligned} \pmatrix{6&0\\ 0&6} &= \pmatrix{7&2\\ 2&-1} - 11\pmatrix{7&2\\ 2&-1}^{-T},\\ \pmatrix{8&0&0\\ 0&-8&0\\ 0&0&-4} &= \pmatrix{7&-2&0\\ 2&-1&0\\ 0&0&-1} + 3\,\pmatrix{7&-2&0\\ 2&-1&0\\ 0&0&-1}^{-T}. \end{aligned}