@gung is absolutely correct suggesting you multidimensional scaling (MDS) as a preliminary tool to create
points X dimensions data out of distance matrix. I'm to add just few strokes. K-means clustering implies euclidean distances. MDS will give you points-in-dimensions coordinates thereby guaranteeing you euclidean distances. You should use metric MDS and request number of dimensions as large as possible, because your aim is to minimize error of reconstracting the data, not to map it in 2D or 3D.
What if you don't have MDS software at hand but have some matrix functions such as eigenvalue decomposition or singular-value decomposition? Then you could do simple metric MDS yourself - Torgerson MDS, also known as Principal Coordinates analysis (PCoA). It amounts to a bit "twisted" Principal Components analysis. I won't be describing it here, although it is quite simple. You can read about it in many places, e.g. here.
Finally, it is possible to program "K-means for distance matrix input" directly - without calling or writing functions doing PCoA or another metric MDS. We know, that (a) the sum of squared deviations from centroid is equal to the sum of pairwise squared Euclidean distances divided by the number of points; and (b) know how to compute distances between cluster centroids out of the distance matrix; (c) and we further know how Sums-of-squares are interrelated in K-means. All it together makes the writing of the algorithm you want a straightforward and not a complex undertaking. One should remember though that K-means is for Euclidean distances / euclidean space only. Use K-medoids or other methods for non-euclidean distances.
A similar question.