Hi
Thanks for the sample. This problem is not Joomla or sh404SEF related. You have a major issue on your web server setup, which is the one triggering the 404:
[xxxx]
For some reason, your web server does not accept those URLs, and rejects them without passing them on to Joomla. If this started to appear a couple of months ago, it's probably an update/change in configuration by your hosting company (it happens frequently). The screenshot shows € and other signs, so this might be related to a change in the server character set maybe. This may also be coming from updates to your .htaccess file though, things like Akeeba Admin tools, or similar which write to the .hraccess file ( less likely than hosting, but still quite possible).
I would suggest to contact your hosting company ASAP.
When I did the last update it did flag me that I had a mix-up between settings on Joomla and sh404sef. It seems it was "Adds Suffix to URL" that was off and that seemed to make it happy.
This warning has been there for a long while. It warns you (this is not an error, just a warning), that you should always configure Joomla and sh404SEF the same: if you have set Joomla to add a suffix to URls, you should also add a suffix in sh404SEF. Likewise if you don't have a suffix in Joomla, you should not have one in sh404SEF.
This will not alter the way sh404SEF operates, but other extensions may be affected in rare cases, and not build URLs as expected.
Rgds