I think the story where abelian, i.e. $U(1)$, gauge symmetry comes from is pretty straight-forward:
We describe massless spin 1 particles, which have only two physical degrees of freedom, with a spin 1 field, which is represented by a four-vector. This four-vector has 4 entries and therefore too many degrees of freedom. A description of a spin 1 particle in terms of a four-vector field is necessarily redundant and we call this redundancy "gauge symmetry". Formulated differently: particles are representations of the little groups of the Poincare group, whereas fields are representations of the complete Poincare group. This is what leads to the gauge redundancy. However, as far as I know this story only works for the familiar $U(1)$ symmetry.
(This point of view is emphasized, for example, in Weinbergs QFT book Vol. 1 section 5.9. Someone who currently likes to emphasize this perspective is Arkani-Hamed, for example, in section 2 of his latest paper: https://arxiv.org/abs/1709.04891 or here https://arxiv.org/abs/1612.02797. I actually asked him a month ago if he knows any idea for an analogous explanation for non-abelian gauge redundancies, but unfortunately he didn't had a good answer.)
Is there any similar idea where non-abelian gauge symmetries come from?
The big difference, I think, is that non-abelian gauge symmetries also in some sense help us to explain the particle spectrum. For example, we have doublets and triplets of elementary particles and this is a real physical consequence and can not be regarded as an accident, because we use the "wrong" objects to describe elementary particles.