Variance in cross validation score / model selection
Since you want your model to be a general solution, you want to include all your data when building the final model.  You are correct in saying that keeping the model with the best validation score in the CV is overfitting.  Including these inner random states help generalize your model, and since you have already tuned your model parameters using CV, you can apply these parameters to the final model. 

As for feature selection, you want to separate the data used to perform feature selection and the data used in cross-validation, so feature selection is performed on independent data in the cross-validation fold.  This prevents biasing the model.  If you were to select your features on the same data that you then use to cross-validate, you will likely overestimate your accuracy.

Here are some other great posts that help:
https://stats.stackexchange.com/questions/11602/training-with-the-full-dataset-after-cross-validation

https://stats.stackexchange.com/questions/27750/feature-selection-and-cross-validation

Check out Dikran Marsupial's answers to both, they are really good.