This feels like a modified Boyer-Moore string search:
You're basically trying to prove that matching S2 to different positions of S1 won't work with any set of substitutions (or won't work with the known characters), which allows you to skip them and move on.
In your specific example, you know that you need to match 5 chars. Your string S1 has 2 places where it could be anything, with 5 places in the middle. So, if you can match the left 4 characters in S2 to something that doesn't include an x in S1, or the right 4, you can then test the last character only. (Neither works here.)
If you had a string of 5 x's "xxxxx" and all of the characters in S2 where also found in the list of acceptable characters, then you have an automatic match.
To make this generic, you could search for all occurrences of x in S1, then attempt to match on the left or right side to S2, then fill in the blanks as needed. If you had 2 occurrences of x in a row, you'd only need to search the left or right 3 chars of S2 (in your specific case.) To search in the middle, you end up sliding S2 across the x found and attempting to match to the left and right.
Only when the characters in S1 that are specific match do you then need to do substitutions.
If all characters in your substitution list are in S2, you don't need to do substitutions at all, the string matches the position.
You can skip lining up positions where S2 has a character not in the substitution list that lands on a degenerate character.
I don't have any pseudo code, so I'm not sure of running time.