Learning a small disjunction using an input distribution of our choice
$\Theta((k+1) \lg n)$ pairs are sufficient.  I think this is the best that's achievable.

Here's the distribution $D$ that achieves this result.  Let $p = 1/(k+1)$ and choose each bit of $x$ from Bernoulli(p) (i.i.d.), i.e., each bit of $x$ is $1$ with probability $p$ and $0$ otherwise.

Call $x$ good if $f(x)=0$.  Note that if $x$ is chosen according to $D$, it has probability $(1-p)^k$ of being good.  This is $(1-1/(k+1))^k$, which is approximately $e^{-1}$ (using the standard approximation $(1-y)^z = e^{-yz}$).  So, $\Pr[f(x)=0] \approx 1/e$, and about a constant fraction of pairs are good.

Now we can take all of the good pairs we have, and look for bit positions that are consistently zero in every good pair.  If we have enough good pairs, only correct positions $i_1,\dots,i_k$ should remain.  Fix a particular incorrect bit position; it has a probability $p$ of being eliminated by each good pair, so the probability that it survives all the good pairs is $(1-p)^g$, where $g$ is the number of good pairs.  Taking $g = -2\lg(n)/\lg(1-p) \approx 2 \lg(n)/p$, we find that the probability of survival for a single incorrect bit position after all $g$ good pairs is $1/n^2$.  By a union bound, this means the probability that any of the incorrect bit positions survive is about $1/n$.  In other words, if we have $2\lg(n)/p$ good pairs, with overwhelming probability this procedure will succeed in correctly inferring $i_1,\dots,i_k$.

Putting these two together, we need about $2e \lg(n)/p$ pairs.  Since $1/p=(k+1)$, this is $\Theta((k+1)\lg n)$.

It's possible to show that this is the best possible value of $p$.  Define $f(p) = p (1-p)^k$.  Then
$$f'(p) = (1-p)^{k-1} (1-(k+1)p),$$
since $f'$ is zero at $p=1/(k+1)$, and one can verify that the maximum value of $f(p)$ on the interval $[0,1]$ is attained at $p=1/(k+1)$.  Now the total number of pairs needed by the above procedure is $2 \lg(n)/f(p)$, which is minimal for $p=1/(k+1)$.  This justifies the choice of $p$ suggested above.

I'd conjecture that you can't do better than this class of distributions $D$ (where each bit of $x$ is chosen iid Bernoulli).  If that is right, then it follows that the result given above is the best possible: $\Theta((k+1)\lg n)$ pairs are necessary and sufficient to solve this problem.