What are the origins and differences between these two? Same for Granddad/Grandpa?
Why was there the need for the two different names?
The word nan for grandma is a shortening of the word nana. Both of these words probably are child pronunciations of the word nanny. Etymonline describes this word as originating as a child's word for "female adult other than mother". This is why nanny is used as the word for a caretaker of children (since the 18th century) as well as a grandmother (since the early 20th century). Etymonline also notes that nanna is also a Greek word for aunt.
Grandma has similar origins. The word mama is a child's form of mother. In languages like German and English, the parents of one's parents have the grand- prefix applied to create their names. The original form of grandma was grandmama (18th century, OED). So this is simply the result of applying the grand- prefix to the child word. Then, like ma was derived as a shortening of mama, grandma evolved from grandmama.
As you can imagine, dad and pa/papa are also child words for father.
Why have multiple words
The reason there are all of these names is the same reason why most of us have nicknames for certain people or things based on childhood pronunciations. Whether that means calling your blanket a banky or your sister sessa, most of us form an emotional connection to things from this time period. Even the alternate word for stomach, tummy comes from a child pronunciation. Child language becomes a major part of family life for years, and it makes sense that some words are extended beyond the domain of early childhood development.
We retain these different forms of these words for at least two reasons: (1) each of us gives these words a differing level of significance (who wants to replace the word they use for their loved ones?) and (2) we often have different words for things that we individually use that are appropriate for different registers, e.g. kitty, cat, and feline.
There are many different words for parents and grandparents in English, and I suspect in other languages too. For example "Father", "Pa", "Pop", "Dad", "Daddy".
There are no systematic differences between them, except in terms of formality, and in some cases there are class associations.
In the case of grandparents, many families find it useful to have two different words, which they can then use to distinguish the two grandfathers and the two grandmothers.
The word for "grandmother" in Italian is "nonna". Look at these maps of the distribution of Italian-Americans in the U.S. and the distribution of people who call their grandmothers "nana" in the U.S.. They match very well. In many cases, the root for nan as a nickname for grandmother may be the Italian influence.
Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.
Would you like to answer one of these unanswered questions instead?