Like you already observed yourself, your choice of features (feature selection) may have an impact on which hyperparameters for your algorithm are optimal, and which hyperparameters you select for your algorithm may have an impact on which choice of features would be optimal.
So, yes, if you really really care about squeezing every single percent of performance out of your model, and you can afford the required amount of computation, the best solution is probably to do feature selection and hyperparamter tuning "at the same time". That's probably not easy (depending on how you do feature selection) though. The way I imagine it working would be like having different sets of features as candidates, and treating the selection of one set of features out of all those candidate sets as an additional hyperparameter.
In practice that may not really be feasible though. In general, if you cannot afford to evaluate all the possible combinations, I'd recommend:
Very loosely optimize hyperparameters, just to make sure you don't assign extremely bad values to some hyperparameters. This can often just be done by hand if you have a good intuitive understanding of your hyperparameters, or done with a very brief hyperparameter optimization procedure using just a bunch of features that you know to be decently good otherwise.
Feature selection, with hyperparameters that are maybe not 100% optimized but at least not extremely terrible either. If you have at least a somewhat decently configured machine learning algorithm already, having good features will be significantly more important for your performance than micro-optimizing hyperparameters. Extreme examples: If you have no features, you can't predict anything. If you have a cheating feature that contains the class label, you can perfectly classify everything.
Optimize hyperparameters with the features selected in the step above. This should be a good feature set now, where it actually may be worth optimizing hyperparams a bit.
To address the additional question that Nikolas posted in the comments, concering how all these things (feature selection, hyperparameter optimization) interact with k-fold cross validation: I'd say it depends.
Whenever you use data in one of the folds for anything at all, and then evaluate performance on that same fold, you get a biased estimate of your performance (you'll overestimate performance). So, if you use data in all the folds for the feature selection step, and then evaluate performance on each of those folds, you'll get biased estimates of performance for each of them (which is not good). Similarly, if you have data-driven hyperparameter optimization and use data from certain folds (or all folds), and then evaluate on those same folds, you'll again get biased estimates of performance. Possible solutions are:
Repeat the complete pipeline within every fold separately (e.g. within each fold, do feature selection + hyperparameter optimization and training model). Doing this means that k-fold cross validation gives you unbiased estimates of the performance of this complete pipeline.
Split your initial dataset into a ''preprocessing dataset'' and a ''train/test dataset''. You can do your feature selection + hyperparameter optimization on the ''preprocessing dataset''. Then, you fix your selected features and hyperparameters, and do k-fold cross validation on the ''train/test dataset''. Doing this means that k-fold cross validation gives you unbiased estimates of the performance of your ML algorithm given the fixed feature-set and hyperparameter values.
Note how the two solutions result in slightly different estimates of performance. Which one is more interesting depends on your use-case, depends on how you plan to deploy your machine learning solutions in practice. If you're, for example, a company that intends to have the complete pipeline of feature selection + hyperparameter optimization + training running automatically every day/week/month/year/whatever, you'll also be interested in the performance of that complete pipeline, and you'll want the first solution.
If, on the other hand, you can only afford to do the feature selection + hyperparameter optimization a single time in your life, and afterwards only somewhat regularly re-train your algorithm (with feature-set and hyperparam values fixed), then the performance of only that step will be what you're interested in, and you should go for the second solution