I don't think it's as simple as saying "the state space explodes, and that's bad".
When you say state space, I think about what is dynamically changing. If you can select one of two design decisions e.g. at compile time then, yes, your state space is bigger, but you don't have to reason about the whole state space jointly. The decision isn't changing at run time.
You have to have tests for all combinations though. At least those combinations that you actually want to use. You get the same problem when your code is a big ifdef-hell.
Testing is important, for sure, but just because you have two parameters with n choices each, does not mean you have to test n^2 combinations. You can aim to express parameterization at a higher level than ifdefs.
For example, template parameters in C++. The STL defines map<K, V>. You don't have to test ever possible type of key and value.
I'm pretty sure that you need n^2 tests if you have n non-equivalent choices each. For maps many types are equivalent so you don't need an infinite number of tests.
If the two hypothetical parameters only affect disparate program logic for some or all of their possible choices, they could require as few as 2n tests instead of the full n^2... If I'm understanding the hypothetical right. (It depends on their potential for interaction.)
When you say state space, I think about what is dynamically changing. If you can select one of two design decisions e.g. at compile time then, yes, your state space is bigger, but you don't have to reason about the whole state space jointly. The decision isn't changing at run time.