The following demonstrates that your basic calculation is correct. In the even case there is a phase transition at $s^{2/n}=1/4$. In the odd case, there is a phase transition somewhere around there. There is a step missing (the "suppose") but I think it should be fillable.
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}$$
Ignore for now the discrete constraint $n \alpha \in \mathbb{N}$. Suppose we can solve $\bar H(a, \alpha) = l$ for $a$ in terms of $\alpha$, then plug into $G$, we have a function of $\alpha$ alone. This function will have a critical point at $\alpha = 1/2$ just by the symmetry of the involved functions around $\alpha = 1/2$. To cut the answer short I suppose that this is the only critical point of this function, and is a a minimum. We can plug this critical point into $G$ and (after some calculation) find $$\color{red}{G(a_*, 1-a_*, 1/2) = 1/2 - s^{2/n}}$$ where $a_*$ is the solution of $H(a, 1-a, 1/2) = l$.
What would this supposition show? In the even case, it shows that your analysis is exactly correct. In the odd case, it shows that your analysis is basically correct, you just have to compare using the closest integer $k$ to $n/2$ (i.e. (n-1)/2). In the odd case, for small enough $s$, you have two solutions because you can put the big eigenvalue in $(n+1)/2$ slots or $(n-1)/2$ slots.