If you want to start removing possibilities you can do that, but if I saw something that wasn't making sense I wouldn't rush to say that certain things are definitely not the cause. You have indications that it is installed correctly, but I wouldn't switch from "indication" to "proof" too quickly, especially considering the lack of success of some of your past assumptions. That being said, maybe everything is fine and the plugin just doesn't work. I haven't been watching you do everything so I can't say what is or is not likely.
So, fix it. Create a second table that is set to the correct character set. Export the data from one table, and then import into the other table. Or, even better, start with clean data and only add your test data. No reason to add a possibility of incorrect data import. The fewer variables the better. This is why people say to create a minimal example showing the problem. The more variables you can eliminate, the easier it will be to figure out. If you have something you suspect might be the problem that you want to test, then test it. Create a test case and test it. Eliminate other variables. In fact, you should start with the absolute minimal setup required and make sure that works. If it doesn't work at all then it's either not installed correctly or it doesn't work.
This is another reason to contact the developers or their community, although I would be surprised if it was anything other than UTF-8.