Average of importance gain for a categorical variable
I think you are looking for information gain.

The way you would compute it for 1 variable is:

Let's say that you label variable is binary.

1) Compute percentages of label per category, for example you have three categories: "US", "UK", "Ger", if there are 5 labels that are marked 1, and 3 of the area associated with "UK", 2 with the "US" and 0 with "Ger", your percentages would be: [3/5, 2/5, 0/5].

2) Do step 1) for every label and aggregate 

3) Calculate entropy for every percentage 

4) Information Gain = Entropy of aggregated percentage - sum of weighted percentages. Weight is just number of instances in a label / total number. For example if we had labels = [1,1,0,0,1,1,0,0,1], entropy of percentages of label 1 would be weighted by 5/9 and entropy of percentages of label 0 would be weighted by 4/9.

Then you compute IG for every variable, and compare!

As a side note, if you are working with a lot of categorical variables, you might want to look into LightGBM or CatBoost, these algorithms allow you to specify categorical variables without creating one hot encoded vectors, and they provide feature importance on these variables.