P-value mining on large number of combinations of variables I really don't know any machine learning, but have a problem that seems like one where I should use some ML algorithm.

I am analyzing a medical study with one age-related condition, age, a treatment, gender, and the abundance of two particular gut bacteria. Many researchers in the field also like to look at the ratio of these two bacteria.

Playing around with some regressions with one, two, or three explanatory variables, I found some unexpected combinations with very good p-values. For instance, controlling for age, bacteria-A seems to be strongly associated with the condition regardless of treatment. The other bacteria seems to be strongly associated with the treatment regardless of age. I would have had no way to expect this to be the case.

I feel there might be value in searching for more unexpected associations. I can make a list of all one, two, and three combination explanatory variables and perform regression of my six variables against these combinations and basically sort by p-value. But, 1) this sort of p-value mining is generally frowned upon, and 2) there are a bazillion possible regressions.

Seems like there is probably some sort of ML algorithm that would hunt down the unexpected associations in an objective and systematic way.

What would that be?
You need to investigate multiple hypothesis correction methods, like Bonferroni correction or Benjamini-Hochberg false discovery rate. The problem with this sort of analysis is that your associations are unexpected, so you don't have any a priori hypothesis. All you can do is test every combination, and then see what is statistically significant after accounting for all the tests.

As you do more tests, it becomes increasingly likely that you'll find an association just by chance alone. To combat this, multiple hypothesis correction methods make the p-value threshold for significance more conservative. If you do only 1 test, a p-value of 0.05 may indicate a significant result. If you do a million tests, however, many of them will have a p-value of 0.05 by chance, so you need to be more conservative. This practice is not generally frowned upon, since it appropriately takes into account the analysis methods. You can easily be dishonest with this approach, however, by doing many tests and only reporting the significant ones without correction.

Obligatory xkcd: https://xkcd.com/882/