Is there any fast algorithm to compute the most similar rectangular regions in two images?
As stated already, you can not do much to speed up a comparison between any two chosen patches. What you need to focus on in order to speed up the process is how to reduce the number of patch pairs you need to compare.

If the computational process is as expensive as I presume it is, in addition to already mentioned image pyramid, I might have another suggestion.

Extract local features and perform feature matching. This is the way to usually recognize similar images, but it works for finding objects in whole images, which means it should also match features in smaller, locally similar patches.

These guys: Sivic, Zisserman: Video Google: A text retrieval approach to object matching in videos had a good idea about spatial consistency. In short, they make sure that the groups of matches have a fairly similar geometrical layout. They use a fairly loose criterion but suggest a way to both loosen and strengthen the criterion. You do have to do a straightforward brute force matching between the feature descriptors, but that still seems far less computationally expensive than directly calculating similarities between patches.

This way, you will hopefully get clusters of matches. Then you could limit the search only to the patches that contain a certain minimal number of matches. In my opinion, these patches would have a substantially higher probability of being the most similar. This is a bit complex add on to make, but I think it could be worth a shot.