Why do languages have gendered nouns? What are the problems that are solved by having gendered nouns?
Properties of individual languages don't necessarily solve problems. Spanish children learn gender of nouns because it would be wrong to say "el aguo", and they learn what their parents say, who in turn learned what their parents said, an so on back to Latin and before.
"Gender" is just one version of noun class systems. It's not clear whether you mean "gender" in the narrow sense (masculine, feminine, neuter; or animate, inanimate), or in the broader sense that also includes for example Athabaskan shape, Niger-Congo classes which cover various semantic properties including. Gender systems seem to have developed historically (over millenia) from systems where the gender distinctions signaled some useful fact such as "is male", "is small", "is alive".