There are some problems associated with k-means here.
First of all, k-means is designed for Euclidean distance. Literally. It does not require triangle inequality, but it requires that the mean minimizes variance. Which might not hold for other distance functions.
Furthermore, the mean of a binary vector -- assuming you try to represent your sets as binary vectors -- will not be a binary vector. So it doesn't map back to a set.
And that can cause artifacts. Essentially, all the means will be somewhere in the center of the data set, much closer to each other than to the actual instances. That is not really what k-means meant to do.
There are tons of distance functions for sets, and an even larger number of clustering algorithms that do not require means to minimize the variance. Try distance based clustering methods. A good starting point is Wikipedia. Hierarchical (but note that these are often implemented in $O(n^3)$, thus slow) and density based (where density is often computed by distance based estimations)
On the scientific side, try this survey:
- Hans-Peter Kriegel, Peer Kröger, Jörg Sander, Arthur Zimek (2011).
WIREs Data Mining and Knowledge Discovery 1 (3): 231–240. doi:10.1002/widm.30