RJ,
As a direct line descendant (grandson), I believe you shouldn't have any issues requesting your grandfather's military records from NPRC.
Just to clarify, on the census the "PA" indicates "filed first papers (declaration of intention to naturalize)" not the state where he filed. He likely filed in New York.
Have you requested his marriage certificate from New York? It may have his parents' names and birth place.
From Valarie's post:
Name Marriage Date Certificate Number County
Pagano Andrea Oct 15 1905 24085 (1905) Manhattan
Demarchis Anna Oct 15 1905 24085 (1905) Manhattan
Ordering NYC Vital Records
New York City Archives
Death records are usually filed in the county where a person passes. So if he died in one of the five boros of New York, you could also order his death certificate from the above if you know the date of death. However, I'm not sure if the death certificate will contain details on his parents' names and birthplace since it appears no one in the family knew that information.
Biff