First, note that it's enough to be able to solve this problem when $k$ is a prime or a power of a prime. That's because, if $k_1$ and $k_2$ are relatively prime, then an abelian group $G$ contains elements of order $k_1$ and $k_2$ if and only if it contains an element of order $k_1k_2$. (That assertion is a good exercise on its own.)
Second, for this specific problem it's crucial to be able to write the isomorphism class of $(\mathbb Z/n\mathbb Z)^*$ in some standard form for finite abelian groups. For example,
(\mathbb Z/3700\mathbb Z)^* &\cong (\mathbb Z/2^2\mathbb Z)^* \times (\mathbb Z/5^2\mathbb Z)^* \times (\mathbb Z/37\mathbb Z)^* \\
&\cong \mathbb Z/2\mathbb Z \oplus \mathbb Z/20\mathbb Z \oplus \mathbb Z/36\mathbb Z \\
&\cong \mathbb Z/2\mathbb Z \oplus \mathbb Z/4\mathbb Z \oplus \mathbb Z/5\mathbb Z \oplus \mathbb Z/4\mathbb Z \oplus \mathbb Z/9\mathbb Z \\
&\cong \mathbb Z/2\mathbb Z \oplus \mathbb Z/4\mathbb Z \oplus \mathbb Z/180\mathbb Z.
The first isomorphism here is by the Chinese remainder theorem. The second isomorphism has to do with odd prime powers having primitive roots, so that these multiplicative groups are cyclic. The third and fourth isomorphisms are again the Chinese remainder theorem; the third line is a standard representation as the direct sum of cyclic groups of prime power order, while the fourth line is a standard representation in terms of invariant factors. (I'm using $\times$ and $\oplus$ interchangeably here ... in the first line the group operation is multiplication, while in subsequent lines the group operation is addition.)
Once you've mastered these items (there are a few different ones, to be sure, but all quite generally important), then answering your specific question should be a breeze.