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