1+1d TSC as $Z_2^f $ symmetry breaking topological order?
So many questions! First of all, it's a bit misleading to describe a Kitaev superconductor as spontaneously breaking $Z_2^f$. In fact, if you put a Kitaev superconductor on a system without boundary (i.e. periodic boundary conditions) there is no ground state degeneracy; the two-fold degenerate ground state for open boundary conditions really should be thought of a boundary modes.
The reason why people sometimes say this is that you can make a non-local transformation (Jordan-Wigner transformation) which relates the Kitaev superconductor to a quantum Ising chain, which does spontaneously break the $Z_2$ symmetry. But the order parameter for the quantum Ising chain doesn't map to anything local in the Kitaev superconductor. Therefore, from a conceptual point of view I think it's better to think of the Kitaev chain as entirely new topological phase and not try to understand it in terms of spontaneous symmetry breaking.
How do you see it's a topologically ordered state? Well, with open boundary conditions it has those topologically protected boundary modes. There is no local term you can add to the Hamiltonian that gaps out those boundary modes. This is not really related to any symmetry; it's just that that those two states are totally indistinguishable unless you look at the whole system so no local interaction could assign them different energies. It is possible to re-interpret this fact in terms of the non-local mapping to the quantum Ising model, but maybe a bit confusing.
To make connection with other definitions of topological order, this topologically protected degeneracy actually implies that you can't smoothly connect the Hamiltonian $H_K$ of the Kitaev superconductor to that of a trivial superconductor, $H_T$, without closing the bulk gap. To see this, we make use of a really useful mathematical trick called quasi-adiabatic continuation [1], which tells you that if $H_K$ and $H_T$ could be smoothly connected without closing the gap, there would exist a local unitary $\mathcal{U}$ relating the ground-state subspaces of $H_K$ and $H_T$. But $H_K$ has a two-fold degeneracy that cannot be closed by a local perturbation, whereas $H_T$ is trivial and therefore there exists a local perturbation $h$ which lifts the degeneracy. But then $\mathcal{U} h \mathcal{U}^{\dagger}$ is a local perturbation which lifts the degeneracy of $H_K$ which is a contradiction.
With regard to your last question, the Kitaev superconductor in 1-D (D-class) is protected without requiring to any symmetry. On the other hand, the class DIII does require time-reversal symmetry. If you ignore the symmetry a class-DIII superconductor actually looks like two copies of the Kitaev superconductor, which is supposed to be trivial (because D class has a $Z_2$ classification). In other words, there are actually two Majorana zero modes on the edge, which is equivalent to a regular complex fermion and can be gapped out. But, the term which gaps out the edge is not allowed by time-reversal symmetry. Thus, the class D superconductor is topologically ordered, the class DIII superconductor is only SPT.
[1] https://arxiv.org/abs/1008.5137
The key question here is that how to define/describe 1+1D fermionic topological order (ie with only fermion-number-parity symmetry $Z_2^f$) for interacting system? Kitaev's approach does not apply since that is only for non-interacting system. In other word, we like to ask "given a ground state of a strongly interacting 1+1D fermion system, how do we know it is topologically ordered or trivially ordered?"
There is a lot of discussions about Majorana chain and topological superconductor, but many of them are only for non-interacting systems. The key question here is how to define/describe those concepts for strongly interacting fermion systems?
A lot of the descriptions in the question are based on the picture of non-interacting fermions, while our 1D chain paper is for strongly interacting fermion systems. Using the picture of non-interacting fermions to view our 1D chain paper can lead to a lot of confusion. Note that there is not even single-particle energy levels in strongly interacting fermion systems, and there is no Majorana zero modes in strongly interacting fermion systems. In this case, how do we understand 1D topological superconductor?
With this background, the point we are trying to make in our 1D chain paper is that:
1) strongly interacting fermion chain that has only $Z_2^f$ symmetry can have a gapped state that correspond to the spontaneous symmetry breaking state of $Z_2^f$.
2) Such a symmetry breaking state is the 1+1D fermionic topologically ordered state (ie is in the same phase as 1D p-wave topological superconductor).
In other words, the 1+1D fermionic topologically ordered state on a chain can be formally viewed as SSB state of $Z_2^f$ (after we bosonize the fermion using Jordan-Wigner transformation). Unlike many other pictures, this picture works for interacting systems.
Also topological order is defined as the equivalent class of local unitary transformations. It is incorrect to say that topological order is characterized by topological degeneracy, since there are topological orders (ie invertible topological orders) that are not characterized by topological degeneracy.