When are these effects executed? My guess is that they are executed immidietly after a player won that story and before any pending stories are resolved. So that you can first win The Other Path story and put a token on a story without success tokens and then resolve that second story and occasionally put more success tokens on it. Am I right?

Rulebook and FAQ doesn't specify that, and it's a bit confusing, because on the one hand won effects should trigger the moment won, and on the other all stories resolve in one gray box on timing chart.

Immediately after. Having two stories with 2 tokens, if they are uncontested, winning The Other Path first pumps those two to 3 tokens, meaning if you have a character of skill 1+ in each, you net all three stories during that Story phase.

Just remember that the active player is the one to choose the order of resolution for struggles and also the resolution for storycards effects.