Yes, DNA testing could be very helpful, although it won't give you a direct answer.
Have an autosomal DNA test done of the oldest generation still living, your grandfather if he is still alive, otherwise one of his children, otherwise you. Meanwhile, build out a family tree of known relatives. For example, if you get DNA from your father, also build out a family tree of your father's mother's family.
When you get DNA matches, ignore them if they are on the side of your known family. what you should pay attention to are DNA matches of unknown relatives. You should then contact these relatives, share what information you have, and ask if they can help. Even if they don't respond, if you have their name, you can start building their family tree using ancestry.com or my heritage.
DNA tests will also be useful for figuring out your paternal grandfather's ethnic heritage, which will affect the search. For example, if he was of European Jewish descent, your search will be harder because of endogamy, which will incorrectly show more close relatives than possible. In my experience, different sites are popular with different ethnic groups. There seem to be a lot more Jews on 23andme than an Ancestry. (I'm Jewish.)
23andMe recently added a nice family tree tool to help you triangulate different matches, but you can use free tools to do the same thing, although it will take work.
Even though Y-DNA is theoretically most useful for determining paternal lines, not enough people have been tested for it to be likely to be useful, or at least that's my experience.
If you can post more information about your paternal grandfather, such as what is known of is ethnicity and where and when he was born, and about the relative that would be tested, that would be helpful, as would your budget and whether you are interested in doing things by hand or want the simplest possible technical solutions.