(Basically) Full answer
- For $s \geq 1$ we always take the matrix with diagonals $s^{1/n}$.
- For $s < 1$ and we have two possibilities. For $n$ small enough we take (still) the matrix with diagonals $s^{1/n}$. For $n$ large enough we instead solve $$a(1-a)^{n-1} = s$$ and take the smaller of the (at most two) solutions. The optimizer will be the matrix with one diagonal $a$ and the rest $1-a$. (Note for $s$ small enough we will have $a \approx s$ and $dist \approx 1$.
Intuitive optimizers
First, to get some intuition for the problem realize that the behavior of the solution is going to depend on $s$. If $s$ is very large, then it is best to take all the eigenvalues equal. This is easy to visualize: the closest point on the graph of $xyz=1000$ to $(1,1,1)$ is $(10,10,10)$.
On the other hand, if $s$ is very small then taking all the values the same gives a distance of about $n$. By taking one eigenvalue to be $s$ and the rest to be $1$ we can have a distance of $1$ from the identity.
Dimensionless problem
We pick up from your optimization problem (1). It is convenient to write $\alpha = k/n$ and $L = \log(s)/n$ so that your optimization problem is equivalent to minimizing $$G(a,b,\alpha) = \alpha (a-1)^2 + (1-\alpha) (b-1)^2$$ over the set $$H(a,b,\alpha) = L, \quad a>0,\quad b>0,\quad \alpha \in [0,1], \quad n\alpha \in \mathbb{N}$$ where $H(a,b,\alpha)$ is $$H(a,b,\alpha) = \alpha \log (a) + (1-\alpha) \log (b).$$
We can perform the method of Lagrange multipliers in the $a$ and $b$ coordinates. This will give us that either $b=a$ or $b = (1-a)$. A more direct path to this result is to observe in your equation $$\sigma^2 - \sigma - \lambda = 0 \text{ for some } \lambda \in \mathbb{R}$$ we have that if $\sigma$ is a solution, so is $(1-\sigma)$.
The easy competitor
Now if $a = b$ then $\alpha$ is irrelevant, and we have the first competitor to the minimization $$a = b = e^L, \quad \alpha = \text{anything}, \quad dist = (e^L-1)^2$$
The harder competitor The case $b = 1-a$ is harder to analyze. First note that for this solution we must restrict to $a < 1$. Given that $b = 1-a$ we can rewrite our optimization as minimizing $$\alpha (a-1)^2 + (1-\alpha)a^2 $$ over the set \begin{equation}\tag{1} \alpha \log(a) + (1 - \alpha) \log(1-a) = L \end{equation} \begin{equation} \tag{2} a \in (0,1/2), \quad a \leq \min(e^L, 1-e^L), \quad n\alpha \in \mathbb{N} \end{equation} The first constraint above comes from assuming (WLOG) $a$ is smaller than $b$. The second is from observing that $L$ is a convex combination of $\log a$ and $\log (1-a)$ so $\log (a) \leq L \leq \log(1-a)$.
To simplify, we can solve the constraint $\alpha \log a + (1-\alpha)\log (1-a)$ for $\alpha$: \begin{equation} \tag{3} \alpha = \frac{L - \log(1-a)}{\log(a) - \log(1-a)} \end{equation} and now rewrite our minimization as: minimize $$f(a) = \frac{(L - \log(1-a))(1-a)^2 + (\log(a)-L)a^2}{\log(a)-\log(1-a)}$$ over $$a \in (0, \min(e^L, 1-e^L)), \quad n\alpha \in \mathbb{N}$$
Now we claim the following three facts:
- $f(a)$ as zero or one critical points
- $\lim_{a \to 0}f(a) = 0$
- $f(e^L) = f(1-e^L) = (e^{L}-1)^2$
Given these three facts we see that if we forget the condition $n \alpha \in \mathbb{N}$ from our constraints we see that the infimum of $f$ is $0$ which is not realized for $a > 0$. The function $f(a)$ either looks like
or
(These are L = -1/5 and -3.) The red line in these pictures is the value from taking the matrix of diagonals, (e^L - 1)^2.
If we now enforce the discrete condition $n \alpha \in \mathbb{N}$ we see that it suffices to check the smallest $a$ possible against $(e^L -1 )^2$.
Checking these facts I checked items 2 and 3 with a CAS. For item 1 I did the following. First implicitly differentiate the constraint (1) with respect to $a$ to find $$ \frac{d\alpha}{da} \left(\log a - \log(1-a) \right) = - \left(\frac{\alpha}{a} - \frac{1-\alpha}{1-a} \right) $$ Then differentiate $f$ and set it to zero to find $$ 2 (a - \alpha) \left(\log a - \log(1-a) \right) = (-2a + 1) \left( \frac{\alpha}{a} - \frac{1-\alpha}{1-a} \right) $$ Multiply by $a(1-a)$ to find $$ 2a(1-a)(a-\alpha) \left( \log a - \log(1-a) \right) = (-2a+1) \left(\alpha - a \right) $$ If $\alpha \neq a$ we can divide by $\alpha-a$ and find (checking that there's only one solution) $a = 1/2$. This is disallowed by our constraints (2). On the other hand, we have a solution if $\alpha = a$. Then, check that there is at most one solution to (1) with $\alpha = a$.
Add-on: I will write what I know about $f(a)$ more precisely.
For $L \geq \log (1/2)$ there is a solution to the constraint $\alpha \log a + (1-\alpha) \log (1-a) = L$ with $a= \alpha$. Equivalently, for $1/2 \leq y < 1$ there is a solution to $\frac{a^a}{(1-a)^{1-a}} = y$. There are actually two solutions on $[0, 1]$ related by $a_1 = 1-a_2$, so since we enforce $a<1/2$ there is only one solution on our domain for $a$.
For $L < \log (1/2)$ there is no solution with $a = \alpha$.
This means that $f$ as a function of $a$ has a critical point if $L \geq \log(1/2)$, namely where $a = \alpha$. If $L \leq \log(1/2)$ there is no critical point.
Edit: Here are some pictures for why the smallest value of $a$ below does always corresponds to the smallest value of $\alpha$. I think it's helpful to visualize first. Here is $\alpha$ as a function of $a$ for $L = \log(.99)$, $L = \log(.51)$, $L = \log(1/2)$, and $L = \log(.49)$.
$L = \log(.99)$
$L = \log(.51)$
$L = \log(.5)$
$L = \log(.49)$
If $L \leq \log(1/2)$ then $\alpha$ as a function of $a$ has no critical points and is increasing (similar reasoning as with $f(a)$). Therefore taking the smallest possible $\alpha$ gives you the smallest possible $a$.
If $L > \log(1/2)$ then for $a \in [0, 1-e^{L}] = [0, min(e^L, 1-e^L)]$, $\alpha$ has a single critical point, a maximum, and is zero at the endpoints. Therefore, we can (mistakenly) choose $\alpha = 1/1000$ and then take $a$ to be large. But, you can visualize all allowable values of $a$ by drawing a discrete collection of horizontal lines on this picture (here's $L = log(.51), n=10$):
The possible choices of $a$ in our discrete set are given by intersections of the red lines with our blue curve, by the nature of the function each red line has two intersections with the blue curve. The lowest red line has both the smallest and largest value of $a$. This picture also illustrates how to find the counterexample to your stackexchange question.