Without profiling, it is hard to say where the speed difference is, it could be in the switch out to AppleScript, or it could be in the creation of the action, especially in the conversion of the base64 back in to an image. Or it could be something else.
You could try a similar test with a trivial action, and see what affect the Execute AppleScript has, then you could try a similar test with the trivial action containing a disabled version of your action so that the creation of the action, including the decoding of the base64 all has to happen, but not the actual execution of the action, and then you could try a similar sized action and see how its performance compares.
But realistically, Keyboard Maestro is not designed with high speed performance as a primary goal.
The question would be, if the image was stored in an image file and read by Keyboard Maestro, or if the image was stored in a Named Clipboard, what would the performance be like, and I don't have an answer for that, and frankly it wouldn't be the design goal for implementing either of those features, it would simple be enhancing the power of the action. Executing XML is a sort of “catch all” to allow you to go beyond what Keyboard Maestro currently enables, but I am always attempting to add more power to what Keyboard Maestro enables, and that would be why I'd implement the features, not speed per se.
As far as implementing those features, the primary issue is UI. The actions containing these found image searches are already very complex, adding another selector and associated fields to enable the image to come from places like Named Clipboards or a file would add even more complexity.
An alternative approach, assuming you have a fixed set of 40 images is to just create a fixed set of 40 actions. The actions can be created via AppleScript from a folder full of images, so it is possible to set it up in such a way that you could change the images and then automatically re-create the actions.