The first approach is actually hold out evaluation (although CV is used for tuning) and the second approach is cross validation IF you just consider the hyperparameters (eg, the feature importance and number of features and K, etc.) to be parameters of some modeling process that you intend to evaluate using cross validation. This is explained well in How to get hyper parameters in nested cross validation?.
If conceptualized this way, the answers in Hold-out validation vs. cross-validation become directly relevant. Some major benefits:
If you use hold out, you "lose" the testing data (in contrast, CV allows you to make statements about the generalization error of the model trained on the full dataset, so you don't waste any data). Sample size is a major consideration here, and I think with 150 observations the recommendation would be to use CV.
CV with its multiple folds gives a sense of the variability of the feature selection/hyperparameter optimization process as well as some measure of variability of performance. Clearly a modeling process with 0.90 accuracy $\pm$ 0.20 is not the same as 0.90 $\pm$ 0.02.
Another method that gives similar benefits is bootstrap: see Cross-validation or bootstrapping to evaluate classification performance?. This page also discusses that accuracy even without class imbalance is a poor scoring rule.
One difficulty with CV for modeling process evaluation (eg, nested CV) is that it requires that you, expectedly, automate your entire modeling process. So, anything that is subjective or manual is pretty much out of the question. Sometimes, domain expertise can only be integrated manually. Further, hyperparameter search must be automated, which is fairly easy, but so must be the search for the hyperparameter search space. For example, if you find in some fold F that your chosen K (for kNN) is actually at the border of your search space, you might want to expand the search space. If you don't do this, your comparison between kNN and SVM will not be valid because it's possibly that you gave SVM a better search space than you gave kNN. This search space expansion can only be done within fold F; there will be leakage if you have a globally defined search space used for all the folds that you change after seeing this (see Does changing the parameter search space after nested CV introduce optimistic bias?). This might take much longer to run (and be considerably more difficult to program) than a simple hold out.
Determining the number of epochs by e.g. averaging the number of epochs for the folds and use it for the test run later on?
Shortest possible answer: Yes!
But let me add some context...
I believe you are referring to Section 7.8, pages 246ff, on Early Stopping in the Deep Learning book. The described procedure there, however, is significantly different from yours. Goodfellow et al. suggest to split your data in three sets first: a training, dev, and test set. Then, you train (on the training set) until the error from that model increases (on the dev set), at which point you stop. Finally, you use the trained model that had the lowest dev set error and evaluate it on the test set. No cross-validation involved at all.
However, you seem to be trying to do both early stopping (ES) and cross-validation (CV), as well as model evaluation all on the same set. That is, you seem to be using all your data for CV, training on each split with ES, and then using the average performance over those CV splits as your final evaluation results. If that is the case, that indeed is stark over-fitting (and certainly not what is described by Goodfellow et al.), and your approach gives you exactly the opposite result of what ES is meant for -- as a regularization technique to prevent over-fitting. If it is not clear why: Because you've "peaked" at your final evaluation instances during training time to figure out when to ("early") stop training; That is, you are optimizing against the evaluation instances during training, which is (over-) fitting your model (on that evaluation data), by definition.
So by now, I hope to have answered your other [two] questions.
The answer by the higgs broson (to your last question, as cited above) already gives a meaningful way to combine CV and ES to save you some training time: You could split your full data in two sets only - a dev and a test set - and use the dev set to do CV while applying ES on each split. That is, you train on each split of your dev set, and stop once the lowest error on the training instances you set aside for evaluating that split has been reached [1]. Then you average the number of epochs needed to reach that lowest error from each split and train on the full dev set for that (averaged) number of epochs. Finally, you validate that outcome on the test set you set aside and haven't touched yet.
[1] Though unlike the higgs broson I would recommend to evaluate after every epoch. Two reasons for that: (1), comparative to training, the evaluation time will be negligible. (2), imagine your min. error is at epoch 51, but you evaluate at epoch 50 and 60. It isn't unlikely that the error at epoch 60 will be lower than at epoch 50; Yet, you would choose 60 as your epoch parameter, which clearly is sub-optimal and in fact even going a bit against the purpose of using ES in the first place.
Best Answer
Cross Validation is a method for estimating the generalisation accuracy of a supervised learning algorithm.
Early stopping is a method for avoiding overfitting and requires a method to assess the relationship between the generalisation accuracy of the learned model and the training accuracy.
So you could use cross validation to replace the validation set, mentioned in the paper you cite, within an early stopping framework. Ten fold cross validation for instance would be more accurate than using a single validation set, and would normally be a better estimate of generalisation error.
So to summarise, cross validation is a generalisation accuracy measure which could be used as part of an early stopping framework.