Ok, I thought a bit about the problem, and here is another idea. It does not provide an answer, but might give a new idea. Maybe even the sketched algorithm turns out to work well in practice.

Assume we want to find some $n \in \mathbb{Z}$ satisfying $C \le n \le D$ (for some constants $C$ and $D$, which can be assumed to be integers as well) such that $n\cdot y \pmod{x}$ is minimal under this condition.

For that, first use the Extended Euclidean Algorithm to compute the GCD $d$ of $x$ and $y$, as well as integers $A, B$ with $d = A x + B y$. Then we can write $d' = A' x + B' y$ with $d', A', B'$ if, and only if, $d' = d t$ for some $t \in \mathbb{Z}$, and $A' = A t + s y/d$, $B' = B t - s x/d$ with $s \in \mathbb{Z}$.

Hence, we want to make $t \in \mathbb{N}_{\ge 0}$ as small as possible, while keeping $C \le B t - s x/d \le D$ for some $s \in \mathbb{Z}$. Such an $s$ exists if, and only if,
the closed interval $[(B t - D) \frac{d}{x}, (B t - C) \frac{d}{x}]$ contains an integer, or equivalently, if $\lceil(B t - D) \frac{d}{x}\rceil \le (B t - C) \frac{d}{x}$.

Now $\lceil\frac{a}{b}\rceil = \frac{a + (-a \pmod{b})}{b}$, whence $\lceil(B t - D) \frac{d}{x}\rceil = \frac{(B t - D) d + (-(B t - D) d \pmod{x})}{x}$. This is $\le (B t - C) \frac{d}{x}$ if, and only if, $(D - B t) d \pmod{x} \le (D - C) d$.

Therefore, an equivalent problem is finding the smallest $t \ge 0$ such that $$D - B t \pmod{\tfrac{x}{d}} \le D - C.$$

Note that without loss of generality, we can assume that $0 \le B \le \frac{x}{d}$; in fact, in almost every case, we have $B < \frac{x}{d}$ (the only exception is $d = x$ and $B = 1$, $A = 0$, in which $n \cdot y \pmod{x}$ is zero for all $n$). Hence, we can assume that $B d < x$. Moreover, since $1 = A \frac{x}{d} + B \frac{y}{d}$, we see that $B$ and $\frac{x}{d}$ are coprime. In particular, $-B t \pmod{\frac{x}{d}}$, $t \in \mathbb{N}_{\ge 0}$ iterates over every integer the interval $[0, \frac{x}{d})$, including $0$ itself; therefore, we can always find a solution $t$ satisfying $0 \le t < \frac{x}{d}$, which is not surprising when considering the original problem.

One could now proceed as follows, which might lead to an algorithm which is fast in practice (in case $x > (D - C) d$): compute several solutions $t$ by choosing some random $T \le B - C$ and computing $t$ such that $D - B t \equiv T \pmod{\frac{x}{d}}$ (i.e. choose $t \equiv (-T + D) \frac{y}{d} \pmod{\frac{x}{d}}$, since $\frac{y}{d}$ is the modular inverse of $B$ modulo $\frac{x}{d}$) and take the minimum $t'$ over all such $t$. Hoping that at least one of these solutions is small, we are left only with a small interval $[0, t']$ to check for smaller solutions.

[Note that this is a similar problem to the one we started with: we want to find $T \in [0, D - C]$ such that $(-T + D) \frac{y}{d} \pmod{\frac{x}{d}}$ is minimal, instead of finding $n \in [C, D]$ such that $n \frac{y}{d} \pmod{\frac{x}{d}}$ is minimal.]

When we assume that $T \mapsto (-T + D) B^{-1} \pmod{\frac{x}{d}}$ is "random", we can assume that the $t$'s we obtain are randomly distributed in the interval $[0, \frac{x}{d})$, whence $t'$ can be expected to be small. Hence, this algorithm is only faster than just tying all values for $n$ if $t'$ is less than $D - C$, but this can be determined by a simple comparism.