If your footnote texts use a dedicated paragraph style, then I see no problem. You can specify this style in the Find Format field in Find/Change. (And as Chris says, don’t forget to check if “Include footnotes” is actually on.)
That said: if you added that smaller font with a character style, then you have this problem because you stated the smaller size *in* that char style and thus made it work only for a specific base size. You can avoid that by not specifying the actual size in pts, but instead use Horizontal and Vertical Scale in the Advanced Character Formats section. To go from 13pt to 10pt, enter “1000/13” in both the scale fields, and ID will calculate how much that is in %%. (I could have told you to type in “76.9%” but knowing how to get such a value is more useful in the longer run.) Then you can use the same character style for any text size, either larger or smaller, as in your footnotes.