I like this question and the answer, which doesn't seem to appear on either of the pages referenced above, comes from what is called the Ostrowski expansion of a real number (some references use other names for this expansion). This is an analogue of the base $p$ expansion which does for the $d(\cdot, \mathbb{Z})$ distance essentially the same thing that the base $p$ expansion does for the $p$-adic absolute value. I will explain it briefly here.
Assume that $\beta\in [0,1)$ is irrational, let $\beta=[a_0;a_1,\ldots]$ be the simple continued fraction expansion of $\beta$, and for each $n\ge 0$ let $p_n/q_n=[a_0;a_1,\ldots ,a_n]$ be the $n$th principal convergent. Also for each $n\ge 0$ let $$D_n=q_n\beta-p_n=(-1)^nd(q_n\beta ,\mathbb{Z}).$$ Then, modulo some minor technical details, there is an essentially unique expansion of the form
$$\alpha=\sum_{n=0}^\infty b_{n+1}D_n$$
with $0\le b_{n+1}\le a_{n+1}$ for each $n$ (please note that I said "essentially unique", you can work out the details yourself and I will give a reference at the end of the post).
Next if $k\in\mathbb{N}$ then there is an essentially unique expansion of the form
$$k=\sum_{n=0}^\infty c_{n+1}q_n,$$
with $0\le c_{n+1}\le a_{n+1}$ for each $n$.
Now since the quantity $d(\cdot,\mathbb{Z})$ is invariant under integer translation we have that
$$d\left(\alpha-k\beta,\mathbb{Z}\right)=d\left(\alpha-k\beta+\sum_{n=0}^Nb_{n+1}p_n,\mathbb{Z}\right),$$
for any $N\ge 0$. Thus if $c_{n+1}=b_{n+1}$ for all $n< M$ (actually I think you technically have to assume $M\ge 4$ here) then it follows that
$$d\left(\alpha-k\beta,\mathbb{Z}\right)=d\left(\sum_{n=M}^\infty (b_{n+1}-c_{n+1})D_n,\mathbb{Z}\right).$$
Finally since the quantities $D_m$ decrease at least exponentially it is not difficult to show that for $M\ge 4$ or $5$,
$$d\left(\sum_{n=M}^\infty (b_{n+1}-c_{n+1})D_n,\mathbb{Z}\right)\asymp |b_{M+1}-c_{M+1}|\cdot |D_M|\asymp \frac{1}{q_M}.$$
The $\asymp$ sign here means that the left hand side is bounded above and below by positive constants times the right hand side.
So that in a nutshell is the answer to your question. You start with the Ostrowski expansion of $\alpha$ with respect to the continued fraction expansion of $\beta$, choose $M$ so that $1/q_M<\gamma$, and then any integer of the form
$$k=\sum_{n=0}^{M-1}b_{n+1}q_m+\sum_{n=M}^Nc_{n+1}q_n,$$
with $0\le c_{n+1}\le a_{n+1}$ will be a solution to your inequality, modulo some universal constant and the minor technical points about the expansion that I mentioned above.
In particular to answer your question about the smallest integer which satisfies your inequality, assuming $\gamma$ is not too large (otherwise the problem is easy anyway), it will be given by choosing $M$ to the first integer such that
$$k=\sum_{n=0}^{M-1}b_{n+1}q_m$$
satisfies the inequality. Also, everything here is explicitly computable from the continued fraction expansion of $\beta$.
For more technical details about the universal constants involved and about the restrictions on the digits necessary to get a unique Ostrowski expansion, see the book Continued Fractions by Rockett and Szusz. They call this the $t$-expansion of a real number.