You can use a single binding, but with a different value depending on which state you’re in.
If you click on the binding, and select “Target” in the state behaviour panel, the target of the binding (which includes the program change value) will be dependent on song state. In other words, once that’s set, if you enter a program change value in the first state, and a second program change value in the second state, when you alternate between the two states, you’ll see the program change value change. This is the essence of state behaviours…
Not sure why trying to use “Selected program” state behaviour with your Kontakt plugin didn’t work. That’s the standard way to choose plugin presets or rack states, driven by song states. Perhaps it’s a peculiarity with Kontakt. Do you have your Kontakt programs arranged in a bank?