I realized that once we suppose $\kappa$, $|\mathcal{X}|$ and $|\mathcal{Y}|$ are all $O(1)$, there is a much simpler argument. For each entry of the matrix that is not in the last column, pick a number from $[-\sqrt n,\sqrt n]$ and select the last number of each row such that the marginal becomes $t$. This gives the required $\sqrt n^{(|\mathcal{Y}|-1)\cdot|\mathcal{X}|}$.
For completeness, here is my $Old$ $answer$: I think they use the following fact: The number of ways to put A (identical) balls into B (ordered) bins is ${A+B-1 \choose B-1}$. If A is big compared to B, this is about $A^{B-1}$. More precisely, I think they suppose $|\mathcal{X}|$ and $|\mathcal{Y}|$ are both $O(1)$. Here is a sketch of the computation (not rigorous at all!!!):
In the problem, first we have to decide in which rows the at most $\kappa \sqrt n$ difference will appear, so we put at most $\kappa \sqrt n$ balls to $|\mathcal{X}|$ bins, so far, omitting $\kappa$ and summing for the number of balls from 0 to $\sqrt n$, about $\sqrt n\cdot \sqrt n ^{|\mathcal{X}|-1}= 2^{|\mathcal{X}|\log n /2}$ possibilities. Obviously in most cases this distribution will be quite even, so in each row we further have to divide $\kappa \sqrt n/ |\mathcal{X}|$ balls into $|\mathcal{Y}|-1$ bins and then use the last bin to make the marginal equal to $t$, so we get (ignoring $|\mathcal{X}|$ as it is $O(1)$) about $2^{(|\mathcal{Y}|-2)\log n /2}$ possibilities in each row. In total $2^{|\mathcal{X}|\log n /2} \cdot (2^{(|\mathcal{Y}|-2)\log n /2})^{|\mathcal{X}|}$, just what we wanted.