Without confirmation that Grandfather was in fact from Kyiv, moving your research to Ukraine is not a good idea, at least for the right now.
A simple search costing $500 is a rip off. You can hire a local and get the whole tree done, even in Kyiv.
Was Grandfather Orthodox or Greek Catholic? Did he have a social security card? Application for Social Security required mother's maiden name.
Were his children baptized in an Orthodox Church? Russian Orthodox Church records were very detailed, including names of Parents, Grandparents and GGrandparents, where they came from and what they did for a living.
According to census, Grandfather had a 4th grade education in Kyiv??? In Grandfather's time frame, it was an average education for peasants. Was he a blacksmith in the old country?
LDS has filmed Russian Orthodox Church Registers for 4 or 5 Orthodox Churches in Kyiv.