Pictures are only forbidden if made for idolatry
Rambam, Hil. Avodah Zarah 7:6:
צוּרוֹת שֶׁעֲשָׂאוּם עוֹבְדֵי כּוֹכָבִים לְנוֹי מֻתָּרִין בַּהֲנָאָה וְצוּרוֹת שֶׁעֲשָׂאוּם לַעֲבוֹדַת כּוֹכָבִים אֲסוּרִין. כֵּיצַד. כָּל הַצּוּרוֹת הַנִּמְצָאִים בַּכְּפָרִים אֲסוּרִים בַּהֲנָאָה מִפְּנֵי שֶׁחֶזְקָתָן שֶׁלַּעֲבוֹדַת כּוֹכָבִים הֵן עֲשׂוּיִין, וְהַנִּמְצָאוֹת בַּמְּדִינָה אִם הָיוּ עוֹמְדִין עַל פֶּתַח הַמְּדִינָה וְהָיָה בְּיַד הַצּוּרָה צוּרַת מַקֵּל אוֹ צִפּוֹר אוֹ כַּדּוּר אוֹ סַיִף אוֹ עֲטָרָה וְטַבַּעַת חֶזְקָתוֹ שֶׁהוּא לַעֲבוֹדַת כּוֹכָבִים וְאָסוּר בַּהֲנָאָה. וְאִם לָאו הֲרֵי הוּא בְּחֶזְקַת לְנוֹי וּמֻתָּר:
Pictures that a non-Jew made for decoration are permitted for benefit, and pictures made for idolatry are prohibited. How so? Any pictures found in villages are forbidden for benefit, because their presumption is that they were made for idolatry. Those found in large cities, if they are standing at the entrance of the city, and in the hand of the image is a figure of a stick, bird, globe, sword, or crown and ring, its presumption is for idolatry and is forbidden to benefit, and if not, it’s in the presumption of [being made] for decoration and is permitted.
So if it was made for decoration, or can be presumed that it was made for decoration, even the painting is permissible, and certainly its frame.
But what if it is made for, or can be presumed to have been made for, idolatry?
Idols are only forbidden immediately if made by a non-Jew
If the painting was made by a Jew, seemingly even the painting - and certainly the frame - would be permitted until someone actually worships it. If the painting was made by a non-Jew, then the painting is forbidden immediately, at which point your question starts. As per ibid. §4:
מַה בֵּין עֲבוֹדַת כּוֹכָבִים שֶׁל עוֹבֵד כּוֹכָבִים לַעֲבוֹדַת כּוֹכָבִים שֶׁל יִשְׂרָאֵל. עֲבוֹדַת כּוֹכָבִים שֶׁל עוֹבֵד כּוֹכָבִים אֲסוּרָה בַּהֲנָאָה מִיָּד שֶׁנֶּאֱמַר (דברים ז כה) "פְּסִילֵי אֱלֹהֵיהֶם תִּשְׂרְפוּן בָּאֵשׁ" מִשֶּׁפְּסָלוֹ נַעֲשָׂה לוֹ אֱלוֹהַּ. וְשֶׁל יִשְׂרָאֵל אֵינָהּ אֲסוּרָה בַּהֲנָאָה עַד שֶׁתֵּעֲבֵד שֶׁנֶּאֱמַר (דברים כז טו) "וְשָׂם בַּסָּתֶר" עַד שֶׁיַּעֲשֶׂה לָהּ דְּבָרִים שֶׁבַּסֵּתֶר שֶׁהֵן עֲבוֹדָתָהּ. וּמְשַׁמְּשֵׁי עֲבוֹדַת כּוֹכָבִים בֵּין שֶׁל עוֹבֵד כּוֹכָבִים בֵּין שֶׁל יִשְׂרָאֵל אֵינָן אֲסוּרִין עַד שֶׁיִּשְׁתַּמְּשׁוּ בָּהֶן לַעֲבוֹדַת כּוֹכָבִים:
What is the difference between a non-Jew’s idol and a Jew’s idol? A non-Jew’s idol is forbidden to benefit from immediately [...] but a Jew’s idol is only forbidden to benefit from once it’s served. [...]
Therefore, if a Jew made it, it’s only forbidden if someone worships it.
The frame is only forbidden if made for the idol specifically
If the frame was made specifically for the picture, there’s no question that the frame has to be trashed as well. To quote ibid. §2:
עֲבוֹדַת כּוֹכָבִים וּמְשַׁמְּשֶׁיהָ וְתִקְרֹבֶת שֶׁלָּהּ וְכָל הַנַּעֲשֶׂה בִּשְׁבִילָהּ אָסוּר בַּהֲנָאָה שֶׁנֶּאֱמַר (דברים ז כו) "וְלֹא תָבִיא תוֹעֵבָה אֶל בֵּיתֶךָ" וְכָל הַנֶּהֱנֶה בְּאֶחָד מִכָּל אֵלּוּ לוֹקֶה שְׁתַּיִם. אַחַת מִשּׁוּם וְלֹא תָבִיא. וְאַחַת מִשּׁוּם וְלֹא יִדְבַּק בְּיָדְךָ מְאוּמָה מִן הַחֵרֶם:
An idol, anything used for serving it, anything offered to it, and anything made on its behalf is forbidden to benefit from, as it says, “Do not bring the abomination to your house.” Anyone who benefits from any of these is liable to two sets of lashes: one for “don’t bring” and one for “Do not stick in your hand anything from the Cherem.”
(7:4 that I cited above does discuss items used for serving the idol being forbidden only once they’re used in idol worship, even if a non-Jew made the idol. As the frame isn’t used to serve the idol, that point seemingly is not relevant here, which is why I left that bit out of my translation above.)
If it’s just an ordinary frame that someone happened to put this painting in, it would seem to be permissible, based on ibid. 8:4:
אִילָן שֶׁמַּעֲמִידִין תַּחְתָּיו עֲבוֹדַת כּוֹכָבִים כָּל זְמַן שֶׁהִיא תַּחְתָּיו אָסוּר בַּהֲנָאָה. נְטָלָהּ מִתַּחְתָּיו הֲרֵי זֶה מֻתָּר מִפְּנֵי שֶׁאֵין הָאִילָן עַצְמוֹ הוּא הַנֶּעֱבָד. בַּיִת שֶׁבְּנָאוֹ הָעוֹבֵד כּוֹכָבִים מִתְּחִלָּה שֶׁיְּהֵא הַבַּיִת עַצְמוֹ נֶעֱבָד וְכֵן הַמִּשְׁתַּחֲוֶה לְבַיִת בָּנוּי הֲרֵי זֶה אָסוּר בַּהֲנָאָה. הָיָה בָּנוּי וְסִיְּדוֹ וְכִיְּרוֹ לְשֵׁם עֲבוֹדַת כּוֹכָבִים עַד שֶׁנִּתְחַדֵּשׁ נוֹטֵל מַה שֶּׁחִדֵּשׁ וְהַחִדּוּשׁ אָסוּר בַּהֲנָאָה מִפְּנֵי שֶׁעֲשָׂאָהוּ לְעָבְדוֹ וּשְׁאָר הַבַּיִת מֻתָּר. הִכְנִיס עֲבוֹדַת כּוֹכָבִים לְתוֹךְ הַבַּיִת כָּל זְמַן שֶׁהִיא שָׁם הַבַּיִת אָסוּר בַּהֲנָאָה. הוֹצִיאָהּ הֻתַּר הַבַּיִת. וְכֵן אֶבֶן שֶׁחֲצָבָהּ מִתְּחִלָּה לְעָבְדָהּ אֲסוּרָה בַּהֲנָאָה. הָיְתָה חֲצוּבָה וְצִיְּרָהּ וְכִיְּרָהּ שֶׁתַּעֲבֹד אֲפִלּוּ צִיֵּר וְכִיֵּר בְּגוּף הָאֶבֶן וְאֵין צָרִיךְ לוֹמַר אִם כִּיֵּר עָלֶיהָ נוֹטֵל מַה שֶּׁחִדֵּשׁ וְהוּא אָסוּר בַּהֲנָאָה הוֹאִיל וְנַעֲשָׂה שֶׁיֵּעָבֵד וּשְׁאָר הָאֶבֶן מֻתָּר:
In summary, the Rambam discusses two types of cases: 1) a tree that was planted for Avodah Zarah, wherein the tree is forbidden, and 2) a tree that was already there, and an idol was later placed under it, wherein the tree is only forbidden while the idol is under it. Likewise, a house built for Avodah Zarah is forbidden, but if it wasn’t build for Avodah Zarah, and only later an idol was brought into it, or the house was plastered for Avodah Zarah, only the new things have to be removed to permit the house.
So, too, it would seem, the picture frame that was not made for Avodah Zarah would be permitted once the painting is removed. If, however, the frame was made specifically for the idolatrous image, it would be forbidden.
TLDR
- If the image was made for decoration, it’s permitted, and certainly the frame.
- If the image was made for idolatry, but by a Jew, it’s only forbidden once it’s worshipped.
- If the frame was made specifically for a prohibited image, it’s forbidden. Otherwise, it’s permitted once the image is removed.