How to handle categorical features in K-means?

You can quantify correlation, or more precisely association, between categorical variables using something like cross-entropy. There’s an available library dython to compute such association values. Also I am curious why do you want to do clustering ? What is your expected output?

Label encoding is not a good idea if the nature of categories are not ordinal (it is actually not my favorite anyways). Use one-hot encoding and see how it works. You may apply a feature extraction on top of it, e.g. PCA, to reduce the noise coming from sparsity. The other idea is to label categories by their fraction in the feature, for example:

[a,b,b,c,a,a] --> [3/6, 2/6, 2/6, 1/6, 3/6, 3/6]

The best way to encode the data will be through any encoding mechanism like label encoder etc. But before handling the categorical variable check the correlation of a categorical variable with the target variable using the feature selection methods like chi square test with selectKbest.