Just an update: with help from Dan Shepherd and Greg Kuperberg, I now understand how to solve this problem in deterministic, classical polynomial time, *even when the degree $d$ is as large as the field characteristic or larger* (the case that originally interested me, and that David Speyer's excellent answer doesn't treat). As a consequence, I now know that (alas) no exponential quantum speedup is possible for this problem.

For concreteness, let's assume we're working with a degree-$d$ polynomial $p:\mathbb{F}_2^n \rightarrow \mathbb{F}_2$, whose coefficients are given to us explicitly. Our goal is to find the subspace of "secret directions" $s \in \mathbb{F}_2^n$ such that $p(x)=p(x\oplus s)$ for all $x\in \mathbb{F}_2^n$. If $\operatorname{char}(\mathbb{F})$ were large enough, then (as David's answer discusses) we would simply use Gaussian elimination to find those $s$'s for which the formal partial derivative, $\frac{\partial p}{\partial s}$, is the identically-$0$ polynomial. Our problem is that formal partial derivatives are no longer "semantically sane" when $d \ge \operatorname{char}(\mathbb{F})$. For example, over $\mathbb{F}_2$, we can have a formal polynomial like $x^3 + x$ that's constant even though its derivative $3x^2+1=x+1$ is nonzero, or conversely, a formal polynomial like $x^2$ that's non-constant even though its derivative is $2x=0$. Likewise, one can construct examples of polynomials $p:\mathbb{F}_2^3 \rightarrow \mathbb{F}_2$ that have a "secret direction" even though their three partial derivatives

$\frac{\partial p}{\partial x},\frac{\partial p}{\partial y},\frac{\partial p}{\partial z}$

are linearly independent (e.g., $p(x,y,z)=xy+yz+xz+x+y+z$); or conversely, that have no "secret direction" even though their three partial derivatives are linearly dependent (e.g., $p(x,y,z)=xy+yz+xz$).

But we can solve this problem with the help of two new ideas. The first idea is to look at the "finite differences,"

$\frac{dp}{ds}(x) := p(x)+p(x\oplus s)$,

instead of formal partial derivatives. Finite differences are "semantically sane" over $\mathbb{F}_2$; in particular, the problem we're trying to solve is simply to find the subspace of $s$'s such that $\frac{dp}{ds}(x)$ is the identically-$0$ polynomial.

Now, the problem with finite differences is that they don't behave simply under linear combinations: in particular, it's not true in general that

$\frac{dp}{d(s+t)}(x) = \frac{dp}{ds}(x) + \frac{dp}{dt}(x)$.

But this brings us to the second new idea: namely, *the above equation is true "to leading order."* In more detail, $\frac{dp}{ds}(x)$ can be expanded out as a polynomial in both $s$ and $x$, which has total degree at most $d$, and degree at most $d-1$ in $x$ (since the degree-$d$ terms cancel). Now, suppose we look only at the terms of $\frac{dp}{ds}(x)$ that have degree $d-1$ in $x$, and not those terms that involve products of $d-2$ of the $x_i$'s or fewer. Then *those terms will depend linearly on $s$,* since the total degree can never exceed $d$. Thus, letting $q_s(x)$ be the degree-$(d-1)$ component of $\frac{dp}{ds}(x)$, we do indeed have

$q_{s+t}(x) = q_s(x) + q_t(x).$

Now let $S$ be the set of all $s\in \mathbb{F}_2^n$ on which $q_s(x)$ is the identically-$0$ polynomial---or in other words, on which *$\frac{dp}{ds}(x)$ has degree at most $d-2$, considered as a polynomial in $x$.* Then what we learn from the above is that $S$ is a subspace of $\mathbb{F}_2^n$. Moreover, it's a subspace that can be found in polynomial time, by simply using Gaussian elimination to find those $s$'s for which $q_s(x)$ is the identically-$0$ polynomial.

Now, once we've found this degree-$(d-2)$ subspace $S$, we can then simply apply the same algorithm inductively, in order to find the subspace $S' \le S$ of directions $s$ such that $\frac{dp}{ds}(x)$ has degree at most $d-3$, considered as a polynomial in $x$. Once again, the trick is to restrict attention to the "leading-order," degree-$(d-2)$ components of the polynomials $\frac{dp}{ds}(x)$ (for $s\in S$), and then use Gaussian elimination to find the subspace of directions $s$ on which those degree-$(d-2)$ components vanish. (Once again, we take advantage of the fact that these degree-$(d-2)$ components behave linearly as functions of $s$, even though the rest of the polynomials don't.)

Next we find the subspace $S'' \le S'$ of directions such that $\frac{dp}{ds}(x)$ has degree at most $d-4$, and so on, until we're down to the subspace on which $\frac{dp}{ds}(x)$ has degree $0$, and then we're done. Or rather, we're *almost* done: we still need to find the subspace on which $\frac{dp}{ds}(x)$ is the identically-$0$ polynomial, rather than the identically-$1$ polynomial. But that last part is trivial.