Star-free languages is the subset of regular languages that can be described by first-order formulas. Examples of languages separating star-free languages from regular languages are typically given to be "the word is of even length", or similarly "there is an even number of 'a's". Though no first-order sentence can describe such languages, they can be easily described in first-order logic augmented with modular quantifiers. The class of languages expressible in first-order logic with modular quantifiers is itself a subclass of all regular languages, corresponding to languages whose syntactic monoid contains only solvable groups (while star-free languages have aperiodic monoids). What are examples of languages that are not expressible in first-order logic augmented with modular quantifiers?
The reference cited as providing examples is supposed to be "Counter-free automata" by Papert & MacNaughton, however all searches for its text came out empty.
Well, it suffices to take a language whose syntactic monoid is a nonsolvable group, say $S_5$. For instance, you can take the language on the alphabet $A = \{a,b\}$ accepted by the DFA $(Q, A, \cdot, 1, \{1\})$ with $Q = \{1, 2, 3, 4, 5\}$, where $a$ acts as a cyclic permutation and $b$ as a transposition.