VC Dimension generalized to discrete, non-binary, unordered domains?
Yes - I think you are looking for "multiclass VC dimension," and there are a couple different generalizations of VC dimension to multiclass classification.  A good paper on this is by Ben-David et al. ('95). In addition to proving learnability results, they give a nice history and references to previous extensions of VC dimension to the multiclass case.  Another perhaps relevant work by Haussler and Long ('95) generalizes Sauer's lemma to more general versions of VC dimension.