I had an answer in which I assumed something that I do not believe is true.  I can give a partial result though, and I think the computation below is a useful rewrite.

Here is the example which made me realize what was wrong.  For intuition of the phase transition you're observing, consider the case when $s$ is very small (or 0).  Then it behooves you to take your approximating $A$ to have a bunch of entries around $1$, and one very small entry.  This gives us an upper bound on distance of about $1$, for small $s$.  In particular your bound in section 4 is suboptimal (because it is around $n/2$ for small $s$).

----------

Below we consider the problem if we get rid of the dimension and think of $k/n$ as an approximation of a number in $[0,1]$.

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).$$

**The constraint that $n \alpha$ is an integer** is *roughly* like your statement that $F$ decreases as $n$ increases.  (The constraint as written immediately implies, for example, that $F$ is smaller for $2*n$ than for $n$.)

Let's use Lagrange multipliers in the $a$ and $b$ coordinates. The symmetry of the equation means we should be able to actually solve some equations (like a problem in a calculus text).  This method tells us that, for fixed $\alpha$, for some $\lambda$ in $\mathbb{R}$, the optimizer will satisfy 
$$\alpha (a-1)= (\lambda/2) \alpha 1/a$$
$$\alpha (b-1) = (\lambda/2) \alpha 1/b$$
or,
$$a(a-1) = b(b-1)$$
For fixed $a$ this is a quadratic in $b$ and therefore has at most **two real solutions**. In fact the two solutions are $b = a$ and $b=1-a$. (Edit: at this point we have really moved backwards: we are at the point where you realized $\sigma_i$ may have at one or two values.)

**The first** is unsurprising consider either the symmetry of the optimization problem, or the original source.  Coming back to the original problem we have the competitor for the optimization 
$$a = s^{1/n}, \quad \alpha = \text{anything}, \quad \color{red}{G(a, a, \cdot) = (1-s^{1/n})^2}$$
which corresponds to the simple guess of $A$ being a diagonal matrix.  **This is the solution in the top of your case statements.**


**The second** solution $b=1-a$ is more difficult to deal with, but demonstrates the phase transition that you observed in the case $n=2$.  First note that, since we are constrained to positive $a,b$, this competitor does not exist unless there is a solution to $H(a,b,\alpha) = l$ with $a$ and $b$ smaller than 1.  Unwinding definitions this would imply that this competitor only possibly exists in the region $s < 1$. Anyway, now we can reduce understanding these competitors to understanding: optimize
$$\bar G (a, \alpha) := G(a, 1-a, \alpha)$$
over
$$\bar H (a, \alpha) := H(a, 1-a, \alpha) = l, \quad a \in [0,1], \alpha \in [0, 1], n \alpha \in \mathbb{N}$$
Unfortunately, this is as far as I can go now.