I think it's a great idea to make up a list of all the variant spellings that you find for anyone in your research -- including mistakes that happen because of weird indexing and bad OCR.
When we are searching online, we aren't looking directly for the records -- we are searching computer-readable pointers to the records.
Tools for better searching
For searching passenger lists, the gold standard is Stephen P. Morse's One-Step Webpages. Some of the forms offer options to search without the surname at all, or to choose between "starts with or is", "sounds like", or "is phonetically". The latter option has a label which is a link -- click through and you'll find the page Beider-Morse Phonetic Matching (BMPM) which has the source code for developers. The three links at the bottom that page -- the table of tokens, and the two articles on better Soundex, are papers where Beider and Morse explain how it all works.
This paragraph shows which websites have implemented Beider and Morse's improved phonetic matching:
There currently exist several implementations of Phonetic Matching. It is on several databases on my website (http://stevemorse.org) -- namely the Ellis Island database, the Dachau Concentration Camp Records, a database of Jewish surnames, and various naturalization databases. Other websites that have implemented Phonetic Matching are http://sephardicgen.com, http://jewishgen.org, http://jri-poland.org, and http://rtrfoundation.org. In addition, there are several other sites that are currently considering adding Phonetic Matching to their search applications.
Make your own phonetic chart
James Beidler (not to be confused with Alexander Beider cited above) makes up a worksheet when searching for German surnames with all the possible consonant variations and wildcards for vowels. Check genealogy guides for searching for Polish families to see if other researchers have used the same methods. Keep an eye out for software, too -- I once found a wonderful little surname generator (for German surnames) that would make up the kind of list you're looking for.
Misspelled OCR
You may come across a printed index of passenger names that has been converted to computer-readable form via the process of OCR (Optical Character Recognition). Kenneth Marks of the site The Ancestor Hunt has a series of articles that are a tutorial on how to get around bad OCR when searching old newspapers, and a tipsheet showing letter pairs that are often confused.
Hunt's site is well worth exploring if you can't find passenger lists -- very often you can find clues to arrivals of other family members by searching in the social pages of the newspapers, or can narrow down the date of someone's arrival in the US from clues in their obituary.
The set of letter pairs that can be confused in handwritten passenger manifests will be different -- you might be able to find a similar table in articles on reading old handwriting. If I can find a table, I'll link it in here.
Resources and Further Reading
Since we know from your comment on bgwhile's answer that we are looking at the right family, the census records tell us that the naturalization took place between 1920 and 1930. This may not be the case, because the census records may not be accurate. However, if your grandfather did naturalize after 1906, the federal government should have copies of his papers, and the papers may give the name of the ship he arrived on. That information may not be accurate, but sometimes you'll find, as in my husband's family, that the ship name is remembered but the date is not quite accurate -- in any case, it narrows the search window.
To save yourself a tedious search through the area's court records looking for his naturalization, you could request an index search from the USCIS's genealogy program. If they find files about your grandfather, they will send you a letter describing what they have, with instructions about what you need to do if you want to order the actual files. There is a description of the process on the website -- you can also look on the Webinars page to see the dates for the webinars USCIS Genealogy Program Overview and Genealogy Program Index Search Process, which will explain the records held by USCIS, and walk you through the process of making an index request.
Unfortunately there is no way for researchers to search the index online -- there are multiple indexes involved, and the search must be made by the USCIS staff. For a quick overview you can keep on file, download the Genealogy Brochure.
If you make a request, it's in your best interest to do so soon, because the fees may be going up shortly. See Judy G. Russell's post Heads up: fee hike coming.