The differences between K-means, K medians, and K-means on ranks correspond to particular types of use or conclusion you wish to reach. Numerically all three work fine on ordinal data. However, all three lead to conclusions which are less easy to interpret on ordinal scales then they would be for interval scales. For example, K-medians derive their distance measures from the median values of putative groups rather than the means. This will, for many cases, lead to groups that are closer together then would occur under K-means. But the interpretation of what it means to be a part of a cluster defined on an ordinal measure is just as complicated in either case!
If you are looking for a practical way to partition data then any of the three techniques I named will be fine. You should probably do it several ways and compare to better understand your data.
If you are looking for better understanding of the structure of your data you should consider non-metric scaling, correspondence analysis, or specialized ordinal cluster regression techniques (these are used mostly in ecology).