As you've said, all homomorphism are of the form f([x])=[kx], with k an integer. Of course, these maps are only well-defined for certain choices of k. However, it turns out the criteria is not that k be a common factor of n and m.
Specifically, we must have:
x=y (mod n) => kx=ky (mod m)
which its pretty easy to see is equivalent to:
n|z => m|kz
This will be satisfied iff m divides kn. One obvious choice is k=0, which gives the trivial map sending all [x] to [0]. This homomorphism always exists. Another choice is k=m, but this is equivalent to the trivial map since [mx]=[0] in Z_m. In general, we only need to find all the solutions k with 0<=k<m, since solutions differing by a multiple of m are easily seen to give the same map.
Nontrivial values for k will only exist if gcd(n,m)>1. For example, if n=4 and m=6, we can take k=3. Try a few more examples, and hopefully you'll see the pattern that emerges.