I believe that Keyboard Maestro usually matches apps by their Bundle ID, and so if the Bundle ID changes, then it won't be recognized. However, you should be able to just remove the app and re-add it, and it should start to work.
It sounds like you tried that and it did not work for you.
However, you can also tell Keyboard Maestro to match app by path instead of Bundle ID:
Keyboard Maestro does not “cache” the bundle identifier. The bundle identifier is the primary way of identifying an application, and the path is the secondary way, but you can control how applications are matched in the application popup menus.
No, because it is not a per-action setting. It applies to the application and how it is found in the event it is moved or changed.
It applies to applications all over Keyboard Maestro, not only within actions.
The bundle identifier is the recommended approach, since the path would change if the name of the application changes.
Aliases have nothing to do with anything because they would already be resolved.
Keyboard Maestro records the bundle identifier and the path of the application, and as long as neither of them change then you have no issues.
If they change, then by default Keyboard Maestro will look for the application based on the bundle identifier (and the system will find its preferred one with that bundle identifier, which is generally the latest version (or latest created/modified)).
You can choose to force it by bundled identifier or by path. These primarily only apply when you have more than one version of the same application.
But as far as the system (and Keyboard Maestro) is concerned, there is no such thing as an application changing bundle identifier - if its got a new bundle identifier, then it is a new application with just coincidental similarities to the old application.