My mom died before my kids were born. My father remarried after my kids were born. We struggle with the question of names too.
I think to answer this question you need to first ask yourself how important names/titles really are (some would say it's just a name) and then ask yourself how important the person is and how this name would make them feel.
My husband calls his parents by their first names and has never called them "Mom" or "Dad". However, as grandparents, they adopted the title and quite like it!
If I had been more magnanimous, my father's wife would enjoy the title of grandmother. My dad refers calls her "grandma" to the children, but he's the only one. It really doesn't cost us anything. After all, special friends get the title of aunt or uncle!
Since your children are older and haven't know your step-father as grandpa from early on, if you decide to re-name your step-father, I would suggest you hold a re-naming ceremony in the same way that someone is knighted. This could even happen on an auspicious birthday or family occasion. This will give you a chance to formally recognize all that he has brought to your family so that he is honoured, as befits the name.
EDIT: If you are looking for a completely different name that is closer than "Uncle" but more distant than "Grandpa", perhaps you could find a nickname instead; something that is meaningful to your children that also relates to your step-dad. This might be reciprocated by the children getting nicknames too (thus not being "grandchildren"). For example, if they all watch Star Wars movies together, maybe he is referred to as "JediMaster" and they become "the Young Jedi". My cousins called my grandmother "LBBG" (Little Bit Big Grandma) because their other grandmother was much bigger than them. She embraced this and started signing all of her correspondence to us with LBBG!