Grid Search and High Variance
I'm afraid you have to repeat the K-fold CV a few times (with different seeds each time) and average the results. I'd guess that the high variance comes from the small size of the dataset.