Clustering categorical data
k-means is not a good choice, because it is designed for continuous variables. It is a least-squares problem definition - a deviation of 2.0 is 4x as bad as a deviation of 1.0.

On binary data (such as one-hot encoded categorical data), this notion of squared deviations is not very appropriate. In particular, the cluster centroids are not binary vectors anymore!

The question you should ask first is: "what is a cluster". Don't just hope an algorithm works. Choose (or build!) and algorithm that solves your problem, not someone else's!

On categorical data, frequent itemsets are usually the much better concept of a cluster than the centroid concept of k-means.