The solution is motivated by the fact that if $p$ is a prime dividing $\Phi_n(m)$, either $p|n$ or $n|p-1$. We claim that all $k=1009^m-1,m\ge 1$ work. The key claim is the following: for a prime $p\not= 1\pmod{1009}$, all prime divisors $q$ of $u=\frac{p^{k+1}-1}{p-1}$ have $q=1\pmod{1009}$. Note that $(p-1, \frac{p^{k+1}-1}{p-1})=1$ since $(p-1,1009)=1$, so we have that $q|p^{k+1}-1$ but not $q|p-1$. Thus the order of $p$ modulo $q$ is greater than $1$ but divides $1009^m$, meaning $1009|q-1$ as desired. Let $f(n)$ be the part of the number $n$ remaining when we divide out all primes $=1 \pmod{1009}$ from it (this is totally multiplicative). Call the given process operating on $N$ by $p$. We first prove that if $N$ is not divisible by $1009$ initially, then eventually it will be divisible by $2018$. Suppose there existed a number $N$ and a sequence of operations which maintain $N$ not being divisible by $2018$. It will also never be divisible by $1009$ then, because if operating by some prime $p$ caused it to be divisible by $1009$, $p$ cannot be $2$ as $2^{1009^m}-1= 2^1-1=1\pmod{1009}$, so the operation must have been by some odd prime, but operating by an odd prime increases the $2$-adic valuation of the number, so it is also divisible by $2$ and thus $2018$. We claim that the operations in this sequence all decrease the value of $f(N)$. We may never operate by a prime $=1\pmod{1009}$, as operating by this prime would cause the number to be divisible by $1009$. Note that operating by $p$ sends $N$ to $\frac{N}{p}\cdot (p-1)\cdot\frac{p^{k+1}-1}{p-1}$, and so sends $f(N)$ to $f\left(\frac{N}{p}\right)\cdot f(p-1)\cdot f\left(\frac{p^{k+1}-1}{p-1}\right)$. Since $p\not=1 \pmod{1009}$, $f\left(\frac{N}{p}\right)=\frac{f(N)}{p}$ and $f\left(\frac{p^{k+1}-1}{p-1}\right)=1$, and since $f(p-1)|p-1\longrightarrow f(p-1)\le p-1$, the claim is true. But there does not exist a strictly decreasing sequence of positive integers, contradiction, thus when $N$ is not divisible by $1009$ it will eventually be divisible by $2018$. To finish, suppose $N$ is initially divisible by $1009$. If $N$ is divisible by $2$ we are done. Then if we operate by some odd prime $p$, it will increase the $2$-adic valuation of $N$ so it will be divisible by $2$. If it is divisible by $1009$ we are done, if not it reduces to the earlier case.

Amir Hossein wrote: Let $k$ be a given even positive integer. Sarah first picks a positive integer $N$ greater than $1$ and proceeds to alter it as follows: every minute, she chooses a prime divisor $p$ of the current value of $N$, and multiplies the current $N$ by $p^k -p^{-1}$ to produce the next value of $N$. Prove that there are infinitely many even positive integers $k$ such that, no matter what choices Sarah makes, her number $N$ will at some point be divisible by $2018$. We claim that Sarah can choose any $k = 2019^{r} - 1$ for any $r \in \mathbb{N}$. Note that $1009$ is a prime. Let $a_N$ denote the largest divisor of $n$ which is not $\equiv 1(\text{mod 2019})$. Suppose $2018$ doesn’t divide $N$ at any point of time for such a $k$. Claim : $a_N$ decreases with time. Proof. After an operation we have $N’ = N \cdot \tfrac{p^{k+1} - 1}{p}$ where $N’$ is the “new” $N$. Let $q$ be a prime factor of $p^k + p^{k-1} + p^{k-2} + ... + 1$. Note that $ord_q(p) | k+1$. Note that $q \equiv 1 (\text{mod p})$ results in 2018 dividing $N’$. So $ord_q(p) \equiv 1(\text{mod 1009)}$. But this means $a_{N’} = \tfrac{p-1}{p} \cdot a_N$. So, $a_N$ decreases with time. $\square$ $a_N$ is a natural number and shall always remain so. So, $a_N \geq 1$. Thus, $2018$ divides $N$ at some point of time leading to a contradiction as desired. $\blacksquare$

The idea is to create a bunch of $1 \pmod {1009}$ primes, call them good. Write $N = PQ = (p_1^{e_1}\ldots p_m^{e_m})(q_1^{f_1} \ldots q_k^{f_k})$ where $p_i$ are not good primes and $q_i$ are; $P$ is the product of the set of powers of $p_i$ and $Q$ similarly for powers of $q_i$. Note that if at any point, Sarah acts on a prime $q \in Q$, then $q$ is replaced with $q^{k+1} - 1$ in the product, which is even and $0 \pmod {1009}$ so $N$ becomes divisible by $2018$. Say Sarah acts on a prime $p \in P$. Suppose we choose $k$ to be of the form $1009^t - 1$. Then $p$ is replaced by $p^{1009^t} - 1$. Consider primes $p'$ dividing this $-$ we must either have $p' \mid p-1$ or $p' \mid 1 + p + \ldots + p^k$, since\[\gcd(p-1, 1 + p + \ldots + p^k) = \gcd(p-1, k+1) = 1.\]In the latter case, we have $p' \nmid p - 1$ but $p' \mid p^{1009^t} - 1$, suggesting that $e = \text{ord}(p, p') \mid 1009^t$ but is not $1$, so $1009 \mid e$ and $e \mid p' - 1$ so indeed $p'$ is good. Let's get back to Sarah. Once she picks $p \in P$, number $N$ is multiplied by $(p-1)(1 + p + \ldots + p^{k})$ but divided by $p$, where $1 + p + \ldots + p^{k}$ contributes all factors to $Q$. Upon division by $p$, the quantity $P$ loses a factor of $p$ but gains at most a factor of $p-1$, and hence decreases. We keep doing this until $P$ decreases to $1$, at which point we are left with only good primes dividing $N$ and Sarah wins. So all $k = 1009^t - 1$ work. $\blacksquare$