randomForest::importance() already offers two measures of importance:
- the reduction in out-of-bag predictive performance (measured by MSE) if a predictor is permuted randomly
- the total decrease in node impurities from splitting on the variable, averaged over all trees, measured through the Gini index
I personally would trust the first measure more, since the second is "kind of" in-sample.
My recommendation would be to look at measures similar to the first one, using other KPIs than MSE with random permutations of predictors, like proper scoring-rules, either out-of-bag or on an actual holdout sample. (Don't use accuracy.)
Alternatively, fit other models than a random forest, e.g., a logistic regression, and assess standardized parameter estimates.