I worry you have asked the wrong question. In many cases computational resources will not help the guesser. By the time the computations are non-trivial, the chance of winning even with unlimited resources is quite low.
Games where the guesser nearly always loses
If you let $G$ be even a moderately sized symmetric group, then the guesser will almost always lose, even when $k=2$. Larger $k$ just makes the game harder (until $k>m$ and it becomes impossible), so $k=2$ is the easiest version of the game. The easiest version is still hopeless.
The subgroup proposer decides (either privately or publicly) to always choose $m=2$. Even if the guesser knows that $m=2$ and plays optimally (with infinite computing resources), then the probability of winning is given in the following table where $d$ is the number of points of the symmetric group:
$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c} d & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \ldots & 20 \\ \hline 1/p & 1 & 3 & 9 & 25 & 75 & 231 & 763 & 2619 & 9495 & \ldots & 23758664095 \\ \end{array}$ So that by the time $G=S_{10}$, the guesser has only a 1 in 9495 chance of winning, and by the time $G=S_{20}$, the chance has dropped to less than 1 in a billion.
A nicer game, still loses
Suppose the subgroup proposer is nicer and always chooses a bigger subgroup, one that is not contained in any larger subgroup except $G$ itself (and keeps $k=2$). Even if the guesser knows this, he can only improve his chances to: $\tiny\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c} d & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ \hline p & 1/4 & 1/2 & 7/22 & 18/53 & 31/184 & 78/353 & 197/1376 & 360/3977 & 511/363904 & 6343/396498 & 3904/39920896 \\ p & 0.25 & 0.50 & 0.32 & 0.34 & 0.17 & 0.22 & 0.14 & 0.09 & 0.001 & 0.016 & 0.0001 \\ \end{array}$
The probability depends a little on the arithmetic properties of $d$, but overall is decreasing rapidly (especially when $d$ is prime). When $d=17$, I believe the probability of winning has decreased to less than 1 in a million.
Guesser always wins
On the other hand, if $G$ is cyclic of prime power order, then the guesser wins unless the game is patently impossible. The guesser's best strategy does not involve knowing $m$ or $k$. He just guesses elements of $G$ sorted by order (identity first, then elements of order p, then elements of order $p^2$, etc.) until you tell him he has won. The only way he can fail to win is if $k > m$, that is if you make him guess more often then there are actually correct guesses.
Similarly, if $k=1$, then the guesser always wins by choosing the identity element.
Algorithms
To determine if a guess is bad is easy in the symmetric group: this is the so-called “giant test” and is polynomial time. A good strategy would actually involve calculating the entire lattice of subgroups (reasonable only up to $d$ around 10) and choosing elements that have the highest probability of remaining in the subgroup.
Obviously, if one has correctly guessed $x$ and $y$, it would be foolish to guess anything truly new until one had finished guessing every element expressible as a product of $x$ and $y$. In other words, the smart guesser will always enumerate $\langle S \rangle$ before choosing a truly new element. This can be done in polynomial time (via the obvious naive algorithm).
Finding maximal subgroups in symmetric groups can be done quickly, but finding the full subgroup lattice is not feasible beyond $S_{20}$ (and I think $S_{15}$ takes a few days via table lookup).