Since the answer of @Boddle does not give the detail for the case $p \neq 1/2$, I will provide it here.
First off, the geometric approximation still holds for $n \gg d \gg 1$. For $j \geq 0$ we obtain
$$ \mathbb{P}(X_i = d-j) \approx \left(\frac{1-p}{p}\frac{d}{n-d}\right)^j \mathbb{P}(X_i = d).$$
Next, we need to compute $d$ such that $\mathbb{P}(X_i \leq d) \approx 2^{-m}$, which was done by a numerical solving approach, so it will not cause any major difficulty. By summing over all values of $j$, we obtain
$$\mathbb{P}(X_i \leq d) \approx \left(1-\frac{d}{n}\right)\left(1-\frac{1}{p}\frac{d}{n}\right)^{-1}.$$
Following the same procedure as @Boddle suggests, but without multiplying through by $2^n$, we obtain the following equation
$$-\left(\frac{d}{n}+\frac{1}{2n}\right)\log\left(\frac{d}{n}\right)
-\left(1-\frac{d}{n}-\frac{1}{2n}\right)\log\left(1-\frac{d}{n}\right)
-\frac{1}{n}\log\left(1-\frac{1}{p}\frac{d}{n}\right)
+\left(\frac{d}{n}+\frac{1}{2n}\right)\log\left(\frac{p}{1-p}\right) =
-\log(1-p) -\frac{m}{n}\log(2)
+\frac{1}{2n} \left(\log\left(\frac{p}{1-p}\right) + \log(2\pi n)\right).$$
Again defining $\nu = \frac{d}{n} + \frac{1}{2n}$, we obtain an equation of which the solution can be found numerically
$$-\nu\log(\nu) - (1-\nu)\log(1-\nu) -\frac{1}{n}\log(1-\nu/p) + \nu\log\left(\frac{p}{1-p}\right) \\
= -\log(1-p) -\frac{m}{n}\log(2)
+\frac{1}{2n} \left(\log\left(\frac{p}{1-p}\right) + \log(2\pi n)\right).$$
Again, it is clear that the value of $\nu$ depends only on the ratio $\frac{m}{n}$ for large $n$. From the solution of the equation above, we can get to the value of $d$ and $\hat{d}$ and finally we define $\hat{\lambda} = \frac{p}{1-p}\frac{n-\hat{d}}{\hat{d}}$. From here on, the solution is as explained by @Boddle with this change of definition.
It is also useful to give the solution in the case $k \sim \gamma 2^m$, where $\gamma > 0$. We need to find $d$ such that $\mathbb{P}(X_i \leq d) \approx \frac{2^{-m}}{\gamma}$ to maintain $\mathbb{P}(\min X_i > d) \approx e^{-1}$. We can see that nothing changes, except that the equation to solve numerically now becomes
$$-\nu\log(\nu) - (1-\nu)\log(1-\nu) -\frac{1}{n}\log(1-\nu/p) + \nu\log\left(\frac{p}{1-p}\right) \\
= -\log(1-p) -\frac{m}{n}\log(2)
+\frac{1}{2n} \left(\log\left(\frac{p}{1-p}\right) + \log(2\pi n) + 2\log(\gamma)\right).$$
For large $n$, the difference becomes negligible and the solution is approximately the same as above.
I computed the values of $d/n$ as a function of $m/n$ for infinitely large $n$ using the equations above. I show the curves on the plot below for different values of $p \geq 1/2$. This gives an idea of the expected value of the minimum as $k=2^m$ increases relative to m.
