A trivial lower bound is $n/k$, since clearly every horse must race to obtain the answer.

I think we can get $O(n/k)$ upper bound, by adapting the median-of-medians selection algorithm.

First, note that, up to a constant factor, this problem is equivalent to finding the $m$th best horse. For the reduction one way, simply find the $m$ best horses and the $m-1$ best horses and see which horse mysteriously disappeared. For the reduction the other way, find the $m$th best horse, then race every other against it to find which are better and which are worse. (In fact, you don't need to do this - it's not hard to check that if you've found the $m$th best horse through repeated racing, you already know which are better and which are worse.)

For $k=2$, the median-of-medians algorithm is known to give an $O(n)$ time bound, as was pointed out by Ralph Furmaniak. We will also use this to handle $k\leq 4$.

So assume $k\geq 5$ and is odd. Let $T(n)$ be the time it takes to find the $m$th horse among $n$ horses. Then divide the horses into groups of $k$, race them in time $n/k$, and take the median of each. Then select the median of those medians in time $T(n/k)$, and pivot on it in time $n/(k-1)$. (to pivot, the pivot horse must race each other horse only once. This allows us to remove at least $n(k+1)/4k$ of the horses, so we can find the $m$th horse in time $T(n (k+1)/4k)$. So we get:

$$T(n) \leq T\left(\frac{n}{k}\right) + T\left( \frac{n(3k-1)}{4k}\right) + \frac{n}{k}+\frac{n}{k-1} $$

By induction,

$$T(n) \leq \frac{4k}{k-3} \cdot \left( \frac{n}{k}+\frac{n}{k-1} \right) = O \left(\frac{n}{k}\right)$$

In fact we obtain an explicit constant of $8+o(1)$.

This ignores non-unique divisibility, which should only lead to a small error term unless $k$ is very large as a fraction of $n$.