Shuffle the data before splitting into folds
I am running a 4-folds cross validation hyperparameter tuning using sklearn's 'cross_validate' and 'KFold' functions. Assuming that my training dataset is already shuffled, then should I for each iteration of hyperpatameter tuning re-shuffle the data before splitting into batches/folds (i.e., the shuffle argument in the KFold function)?


No, its no needed, shuffling is needed before split.


  I assume that if the outcome depends on shuffling then the model is not robust. Is this correct?


You are right, good model has great performing on every combination of data.


  However, this also may not be 'fair' to the model because the result is not reproducible since the data for each fold is different every time I run cross-validation (i.e., each hyperparameter combination is evaluated on totally different folds. For example, the training/validation dataset in fold #1 of the 1st tuning iteration is different than fold #1 dataset of the 2nd tuning iteration.)


You make cross-validation to check performance on every chunk of data. Your task is achieved most generous model.