There's a Jan Malek in my tree, but with an 1850's birth date he's not likely to be your grandfather. :)
Is that Przemysl origin certain? I ask, because if it's based on immigration or other official records from here in the US, his real origin could easily be Dlugie, or another village in the Przemysl area. (Church records for Dlugie are held in the Przemysl Diocese archives)
Can you shed a bit more light on other family members?