What method(s) should I use to construct the best-performing prediction model with only [k] predictors? I'm interested in doing prediction using the minimal number of predictors, as it will be relatively costly to collect each additional variable for prediction. I have a dataset with 100+ predictors and want to create the optimal model with no more than 5 predictors. How should I go about doing this?
I'm familiar with methods for reducing dimensionality and selecting features such as wrapper and filter methods. But I'm concerned that I could mislead myself by using any method that starts with the best-performing model with 100+ variables and works backwards. Who's to say the best 5 variables from the best-performing all-variable model are the best 5 variables period? Maybe a different model that performs worse with the full number of variables would actually perform better with just 5 variables? Is there a better way to go about doing this than starting with the best-performing model with all possible variables and then working backwards?

The LASSO is a standard way of doing variable selection. Generally, we would do cross-validation to determine the appropriate $\lambda$ and fit our model that way. Instead, you could rely on how the {glmnet} package in R fits a range of $\lambda$ values at once for you—and very speedily. You could then call coef() on your model to get a matrix of all coefficients by the different $\lambda$ values. I would look through the largest value of $\lambda$ that gives you exactly five variables—that is, it estimates the rest of the coefficients to zero.
