Solution:
Note that $1009$ is prime. We will show that if $k=1009^{m}-1$ for some positive integer $m$, then Sarah's number must at some point be divisible by $2018$. Let $P$ be the largest divisor of $N$ not divisible by a prime congruent to $1$ modulo $1009$. Assume for contradiction that $N$ is never divisible by $2018$. We will show that $P$ decreases each minute. Suppose that in the $t^{\text{th}}$ minute, Sarah chooses the prime divisor $p$ of $N$. First note that $N$ is replaced with $\frac{p^{k+1}-1}{p} \cdot N$ where
$$p^{k+1}-1 = p^{1009^{m}}-1 = (p-1)\left(p^{1009^{m}-1}+p^{1009^{m}-2}+\cdots+1\right)$$
Suppose that $q$ is a prime number dividing the second factor. Since $q$ divides $p^{1009^{m}}-1$, it follows that $q \neq p$ and the order of $p$ modulo $q$ must divide $1009^{m}$ and hence is either divisible by $1009$ or is equal to $1$. If it is equal to $1$ then $p \equiv 1 \pmod{q}$, which implies that
$$0 \equiv p^{1009^{m}-1}+p^{1009^{m}-2}+\cdots+1 \equiv 1009^{m} \quad (\bmod q)$$
and thus $q=1009$. However, if $q=1009$ then $p \geq 1010$ and $p$ must be odd. Since $p-1$ now divides $N$, it follows that $N$ is divisible by $2018$ in the $(t+1)^{\text{th}}$ minute, which is a contradiction. Therefore the order of $p$ modulo $q$ is divisible by $1009$ and hence $1009$ divides $q-1$. Therefore all of the prime divisors of the second factor are congruent to $1$ modulo $1009$. This implies that $P$ is replaced by a divisor of $\frac{p-1}{p} \cdot P$ in the $(t+1)^{\text{th}}$ minute and therefore decreases. Since $P \geq 1$ must always hold, $P$ cannot decrease forever. Therefore $N$ must at some point be divisible by $2018$.