How to choose the best hyper-parameter when it is directly influenced by the random_state?

I am assuming, you are taking about the random_state of the Model, not the GridSearch (as it doesn't have a random_state) RandomizedSearchCV do need one.

A random state defines a starting point for an underlying random process.

With an ideal model, the difference should be very small. Though it will be. If it is high, it means there is some Outlier data point/pattern due to which certain value is favoured.

Ignore - if small

If it is large for a specific value
- Check the data
- Increase K for the CrossVal

From another Stackexchange Question

random state values which performed well in the validation set do not correspond to those which would perform well in a new, unseen test set.

From MachineLearning Mastery

We can increase k and build even more models, as long as the data within each fold remains representative of the problem

Links
Stochastic Process
Randomness in ML
Is-random-state-a-parameter-to-tune

If the scoring is very dependent on random_state, it would be better to try to address that rather than choosing a hyperparameter from what you have. You mentioned you used KFold, and that your data is quite small; I suggest trying RepeatedKFold instead.