I found the issue and solution.
Issue: The wiki mentions Accessibility Permission Problem, and correctly allowing access in System Preferences -> Security & Privacy preferences -> Accessibility and enable both Keyboard Maestro and Keyboard Maestro Engine.
When playing around with disabling and re-enabling these, suddenly a popup appeared asking Screen recording rights (sorry, translating from Dutch so might be slightly different naming). Turns out another required checkbox was not set, not allowing KM access to the screen?!?. Keyboard Maestro was not complaining about not having the proper access before I messed with the checkboxes. Also the wiki does not mention the screen recording permission requirement. Maybe Apple changed something?
Solution: In System Preferences -> Security & Privacy preferences go to Screen recording and enable access for Keyboard Maestro there as well.
Now it finds the images just fine with fuzzyness around 20%.