This is known as the complementation property of $DES$; I had thought that it actually predated Biham and Shamir's work.
In any case, your questions:
Does this hold for only that particular combination of $S$-Box or it will be same for any $S$-Box combination?
It'd remain even if you change the $S$-Boxes arbitrarily. The reason for this is that it is not actually caused by the $S$-Boxes. $DES$ generates the inputs to the $S$-Boxes by $XOR$ing $R_i$ with $k_i$. The reason this property holds is if you complement $R_i$ with $k_i$, the result of the $XOR$ won't change, and so the input the to $S$-Box is exactly the same (and hence the output of the $S$-Box is exactly the same).
Also there is one more thing mentioned on the paper, but I am not able to get it.
Actually, that's a fairly straight-forward exploit of this property. I'll see if I can state it more explicitly.
Suppose you knew the ciphertexts for two plaintexts, and these plaintexts happened to be the complement of each other. That is, we know the value $T_1 = E_k(P_1)$ and we also know the value $T_2 = E_k(P_2)$, where $P_1$ and $P_2$ are complements of each other (that is, wherever $P_1$ has a $0$ bit, $P_2$ has a $1$ bit, or in other words, $\overline{P_1} = P_2$
Consider further that we don't know the key $k$; and we'd like to find it.
One thing we can try is pick a random key $k'$, and do a trial encryption of $P_1$ with it. If our $k'$ just happened to be the value $k$, then $E_{k'}(P_1)$ would be $T_1$, and so we know know that $k'$ is likely to be the correct value.
However, consider if our $k'$ is the complement of $k$ (that is, we got every bit wrong). In that case, the key complementation property would hold, and we would have $E_{k'}(P_1) = \overline{E_{\overline{k'}}(\overline{P_1})} = \overline{E_k(P_2)} = \overline{T_2}$, that is, we would see the bitwise complement of $T_2$. So, if we see that value, that also tells us what the key is likely to be.
Hence, by doing a single $DES$ encryption, we can actually test two keys -- that's what Biham and Shamir are pointing out.