What is the relationship between this notion of symmetry compressibility and Kolmogorov complexity?
They are equivalent. For any $x$, let $g_x$ be a permutation with just two cycles: one consisting of $\{i \in [n] : x_i = 0\}$ (say, in ascending order) and one consisting of $\{i \in [n] : x_i = 1\}$ (also in ascending order). Then the "GC" description is just $01enc(g)$, whose length is $2 + K(g)$. But $K(g) \leq K(x) + O(1)$, since the above description of $g_x$ gives a uniform construction of $g_x$ from $x$. So we have $GC(x) \leq 2 + K(g) \leq K(x) + O(1)$.