(in collaboration with hyperbolictangent) It suffices to show that $a^{19}$ and $b^{99}$ range over every odd residue $\bmod{2^{1999}}$ as $a$ and $b$ range over every odd residue $\bmod{2^{1999}}$. $a^{19}$: Consider $z=(a+t\cdot 2^{1000})^{19}$, where $t\in\mathbb{Z}$. Then $z\equiv a^{19}+19at\cdot 2^{1000}\bmod{2^{1999}}$. Since $\gcd(19a,2^{1999})=1$, we know that as $t$ varies, $19at\cdot 2^{1000}$ takes on every residue $\bmod{2^{1999}}$ that is also a multiple of $2^{1000}$. Hence it suffices to show that $a^{19}$ takes on every odd residue $\bmod{2^{1000}}$. We can continue this argument until we eventually arrive at proving that $a^{19}$ takes on every odd residue $\bmod{4}$, which is clear. This proves that $a^{19}$ takes on every odd residue $\bmod{2^{1999}}$. $b^{99}$: Consider $w=(b+s\cdot 2^{1000})^{99}$, where $s\in\mathbb{Z}$. Then $w\equiv b^{99}+99bs\cdot 2^{1000}\bmod{2^{1999}}$. Since $\gcd(99b,2^{1999})=1$, we know that as $s$ varies, $99bs\cdot 2^{1000}$ takes on every residue $\bmod{2^{1999}}$ that is also a multiple of $2^{1000}$. Hence it suffices to show that $b^{99}$ takes on every odd residue $\bmod{2^{1000}}$. We can continue this argument until we eventually arrive at proving that $b^{99}$ takes on every odd residue $\bmod{4}$, which is clear. This proves that $b^{99}$ takes on every odd residue $\bmod{2^{1999}}$. This completes the proof.

This follows quickly; once we have chosen $m$ and $b$, we can choose a sufficiently low (possibly negative) $a$ such that $2m\equiv a^{19}+b^{99}\bmod{2^{1999}}$. Then the choice of a positive $k$ is fixed.