Why do you say "telefonu" here? Don't you usually use it after a preposition like in "do domu"?
We also use this case with negation.
"Ma telefon" but "Nie ma telefonu".
Well, someone called him a telephone but he is not a telephone at all? ;)
But seriously: "He has no telephone" is obviously correct, and unfortunately Duolingo automatically accepts shortening "He has" to "He's" because it works in a sentence like "He has got (He's got) no telephone". That should be considered a bug, but we can't do anything about it on our side. It's strange that it was suggested, after all the only starred option is "He does not have"...
Is there a rule to know when genitive masculine ends with u rather than a or should I just worry about memorizing each word?
Sort of! There are some guidelines. My book says genitive singular masculine 'not alive' words end in 'u'. Exceptions, ending in -a, include: fruit and vegetables, vehicles (eg. ford), currencies, games, cigarettes, tools/containers, body parts, most Polish towns, all months except February, units relating to day (wieczór, dzień), nouns ending in -ek, -ik, -yk (but -ek nouns derived from verbs take -u). So, not easy, but slightly easier than learning separately for each word.
Komórka means mobile phone (it literally means "cell", like the US English "cellphone"); whereas telefon means telephone (komórki is plural or genitive case).