Standard K-means is intended for numeric data and is not directly applicable to other types of objects such as categorical sequences (see for example at that question.)
In sequence analysis, we generally compute pairwise dissimilarities between sequences using one of many possible different metrics (See  for a review.) Although we do not know what the mean of a cluster of sequences could be, we can express the distance to the (virtual) mean of the cluster in terms of pairwise distances between the cluster members (See for instance [2, page 478]). In this way, k-means should be applicable whenever we have a pairwise dissimilarity matrix. Nevertheless, for categorical sequences, pairwise-dissimilarity-based k-medoids is much easier to implement and should be much faster.
Now, regarding the choice of the number k of clusters. I don't think that determining k from the solution of a hierarchical clustering is the best way to proceed. Exploring the k-medoids solutions for a range of k values is much more efficient and it is very easily done with the
wcKMedRange function of the
WeightedCluster R library that returns a whole series of cluster quality measures for the requested set of values k.
 Studer, M., and Ritschard, G. (2016) "What Matters in Differences between Life Trajectories: A Comparative Review of Sequence Dissimilarity Measures", Journal of the Royal Statistical Society, Series A. Vol. 179(2), pp. 481-511 DOI 10.1111/rssa.12125.
 Studer, M., Ritschard, G., Gabadinho, A. & Müller, N.S. (2011), "Discrepancy Analysis of State Sequences", Sociological Methods and Research. Vol. 40(3), pp. 471-510. DOI 10.1177/0049124111415372
TraMineRpackage. I guess the more appropriate question would be why data in the form of sequences might be better suited for K-medoids compared to K-means. I suspect the answer is that there is no "mean" sequence, but there is a medoid sequence. $\endgroup$