I tried to do exactly what you did, and after using AppCleaner to remove all the files, I noticed I still had the open with option left just as you did.
Open up terminal (just type in terminal in spotlight), and try the following commands:
rm -rf ./wine.*
rm -rf ./wine*
rm -rf ./.wine*
rm -rf ./.wine.*
One of these will remove the option for wine to appear, I just wasn't paying attention when I was attempting to get rid of it

so I'm not sure which one. It shouldn't hurt your Mac, mine's working just fine after.
oh, and don't rm -rf ./* by mistake, because that WILL hurt your Mac.