"A girl is looking for a key."
Translation:Dziewczynka szuka klucza.
I expected the same thing is Amnae. If masculine, I would thing genitive for klucz would be kluczu. i.e. hotel ...hotel-u, etc. Thus, making this language BARDZO TRUDNY!!! Always many exceptions to the rule ... trzeba memorize the rule, potem - memorize all the flipping exceptions. Yeesh.
who told you there is any rule for -a/-u ending in masculine genitive? there are some, but they are rather complicated, so the best way is - masculine inanimated nouns can heve -u or -a endings, and you have to learn it by heart.
here are some rules http://lpj.pl/porada13.htm , but the last advice is - less used nouns you should check in dictionary.
All languages are equally difficult (well, except Esperanto, but it is special). The only reason Polish is hard for you is because it is so different than English. If you were a Czech speaker, it would be way "easier" to learn Polish than English simply because you already "know" so much of the language, you just have to apply it.