Feature importance and deriving rules using tree based classification models
You can use categorical features with decision trees in scikit-learn, but you'll need to encode them as numbers. If your categorical features are ordinal (such as ranking ‘bad’, ‘fair’, ‘good’), they are easy to encode in numbers that respect the underlying ordering (e.g. 0, 1, 2). For nominal features, given the high cardinality you mention, you can try some version of the target encoding or the frequency encoding. With the target encoding, make sure to use some form of regularization in order to avoid overfitting.

After the features are encoded, you can build, for example, a random forest and obtain the impact of each feature with attribute feature_importances_.