Here is an earlier effort of Sierpiński: Sur une propriété de la décomposition de M. Vitali, Mathematica 3, 30-32 (1930). He took "Vitali's Decomposition", that is, the family of cosets of $\mathbb{Q}$ in $\mathbb{R}$ and divided it into (unordered!) pairs $\{Q,-Q\}$ of symmetric sets (excluding the one symmetric coset: $\mathbb{Q}$ itself). Given a choice set $\mathcal{Q}$ for this family of pairs let $S=\bigcup\mathcal{Q}$. Then $S$ is non-measurable.
Thus you can get a non-measurable set from AC for pairs, or from the existence of a linear order on the power set of $\mathbb{R}$. He already mentioned the latter in 1917: Sur quelques problèmes qui impliquent non mesurables, C. R. 164, 882-884 (1917).