I would strongly recommend using a network clustering algorithm rather than K-means. K-means is strongly tied to Euclidean distances (and variance minimisation), and what you have is something completely different. A number of well-known network algorithms are Louvain clustering, RNSC, Affinity Propagation Clustering, and MCL.
Strings are a type of data that I think maps well onto networks, as the pair-wise relation is not really based on measurement of traits but rather on direct comparison.
(Another situation where network approaches make sense is in certain types of high-dimensional data). In bioinformatics sequence clustering with string similarity has been very successfully approached using network clustering algorithms. NOTE you need a similarity, not a distance. For more information on K-means and where it is applicable see e.g. Anony Mousse's answer here - Why only the mean value is used in (K-means) clustering method?. Anony Mousse has written about this many times, with great insight.