Welcome to the instability of feature selection. This is totally predictable behavior and one of the reasons why stepwise regression is less of a panacea than it first seems to be. Sure, you select some variables that work well on the training data, and by limiting the variable count to just those that influence the outcome the most, you seem to restrict the opportunity for overfitting, right?
Unfortunately, you put yourself at risk of the variable selection overfitting to the training data. As you can see from your cross validation, just because a set of variables works on one sample does not assure it of working on another. That is, the feature selection is unstable, and with the selected features bouncing all over the place as you make changes to the data (which will be the case when you go predict on new data), there is justifiable doubt that the variables selected based on the training data will be the right variables for making predictions on new data.
If you want to use your model just to predict, then you might be better off bootstrapping the entire dataset, fitting a stepwise model to the bootstrap sample, applying that model to the entire data set, and seeing by how much the performance (on some metric of interest, say MSE or MAE) differs. This is related to the procedure I discuss here. If that is an acceptable amount, you have evidence that the overall stepwise procedure is effective, which can be the case for stepwise regression in pure prediction problems.
If you want to use the stepwise regression to select variables on which you do inferences like p-values or confidence intervals, all of these downstream inferences are distorted by the stepwise selection. While this link mentions Stata software, the theory does not care if you use Stata, MATLAB, Python, R, SAS, or any other software, and the previous sentence relates to points 2, 3, 4, and 7. Briefly, by doing the stepwise regression and then calculating statistics as if you have not, you are performing dishonest calculations that fail to account for the variable selection process.