The Midrashim I quote are all from Bereishis Rabbah 91:6. The main points of the Midrash are quoted by Rashi to Bereishis 42:1 and 42:3; I quote the Midrash because it tells more of the story, but if you just want the gist of it, look at Rashi.
דָּבָר אַחֵר, וַיַּרְא יַעֲקֹב כִּי יֶשׁ שֶׁבֶר בְּמִצְרָיִם, וְכִי בְּמִצְרַיִם הָיָה יַעֲקֹב שֶׁרָאָה תְּבוּאָה בְּמִצְרַיִם, שֶׁאָמַר הַכָּתוּב וַיַּרְא יַעֲקֹב כִּי יֶשׁ שֶׁבֶר בְּמִצְרָיִם, וַהֲלוֹא אָמַר לְבָנָיו (בראשית מב, ב): וַיֹּאמֶר הִנֵּה שָׁמַעְתִּי, אֶלָּא מִיּוֹם שֶׁנִּגְנַב יוֹסֵף נִסְתַּלְּקָה רוּחַ הַקֹּדֶשׁ מִמֶּנּוּ וְרוֹאֶה וְאֵינוֹ רוֹאֶה, וְשׁוֹמֵעַ וְאֵינוֹ שׁוֹמֵעַ, וּמִפְּנֵי מָה לֹא נֶאֱמַר יֶשׁ אֹכֶל בְּמִצְרָיִם, שֶׁאָמַר הַכָּתוּב: כִּי יֶשׁ שֶׁבֶר בְּמִצְרָיִם, וַהֲלוֹא כְּבָר נֶאֱמַר (בראשית מא, נה): וַתִּרְעַב כָּל אֶרֶץ מִצְרַיִם, וּמַה תַּלְמוּד לוֹמַר יֶשׁ שֶׁבֶר, אֶלָא אַל תְּהִי קוֹרֵא יֵשׁ שֶׁבֶר, אֶלָּא יֵשׁ סֵבֶר, שֶׁרָאָה בָּאַסְפַּקְלַרְיָא שֶׁסִּבְרוֹ בְּמִצְרַיִם, וְאֵיזֶה זֶה, זֶה יוֹסֵף.
Another explanation [of] “And Yaakov saw that there was food in Mitzraim.” Was Yaakov in Mitzraim that it says he “saw” grain in Mitzraim, that the passuk says “And Yaakov ‘saw’ that there was food in Mitzraim”? But does he not say to his children “And he said, ‘Behold, I have heard’”?! Rather, from the day that Yosef was kidnapped, Ruach HaKodesh was removed from him; he saw, but didn’t see, heard, but didn’t hear. Because of why does it not say that there was food [אוכל] in Mitzraim, that it says “that there was food [שבר] in Mitzraim”? Is it not already written, “and there was a famine across all of the Land of Mitzraim”? What is the passuk coming to teach us by saying “there is שבר”? Rather, don’t read it as “there was שבר”, but as “there was סבר,” for he saw in a vision that his hope [סבר] was in Mitzraim - and who was this? This was Yosef.
Yaakov couldn’t see prophetically well; he knew there was something in Mitzraim, but couldn’t tell what. The brothers seemed to understand, though, and when they went down, they sought out Yosef.
וַיֵּרְדוּ אֲחֵי יוֹסֵף, בְּנֵי יִשְׂרָאֵל צָרִיךְ הַמִּקְרָא לוֹמַר,
אֶלָּא בַּתְּחִלָּה לֹא נָהֲגוּ בּוֹ אַחְוָה וּמְכָרוּהוּ, וּלְסוֹף
מִתְחָרְטִין וְאוֹמְרִים אֵימָתַי נֵרֵד לְמִצְרַיִם נַחְזִיר אֶת
אָחִינוּ לְאָבִיו, וּכְשֶׁאָמַר לָהֶם אֲבִיהֶם לֵירֵד לְמִצְרַיִם
נָתְנוּ כֻּלָּם דַּעַת אַחַת לְהַחֲזִירוֹ.
“And Yosef’s brothers went down.” The passuk needed to say “the sons of Israel”! Rather, at the beginning, they did not treat him with brotherly love and they sold him; in the end, they regretted it, and they said, “when will we go down to Mitzraim to return our brother to our father? When their father told them to go down to Mitzraim, they all set out with one mind to return him.
So, when the opportunity arises, they jump on it - and they even spend time looking for Yosef before even getting their grain.
מִיָּד אָמַר לָהֶם יוֹסֵף סִתְמוּ אֶת הָאוֹצָרוֹת וּפִתְחוּ אוֹצָר
אֶחָד, וְנָתַן שְׁמוֹתָם לְבַעַל הָאוֹצָר, וְאָמַר לוֹ רְאֵה
כְּשֶׁיָּבוֹאוּ הָאֲנָשִׁים אֵלּוּ לְיָדְךָ תְּפֹשׂ אוֹתָם וְשַׁגֵּר
אוֹתָם לְפָנַי, עָבְרוּ שְׁלשֶׁת יָמִים וְלֹא בָאוּ, מִיָּד נָטַל
יוֹסֵף שִׁבְעִים גִּבּוֹרִים מִבֵּית הַמֶּלֶךְ וְשִׁגֵּר בִּשְׁבִילָם
לְבַקֵּשׁ אוֹתָם בַּשּׁוּק, הָלְכוּ וּמָצְאוּ אוֹתָם בַּשּׁוּק שֶׁל
זוֹנוֹת, וּמַה טִּיבָן בַּשּׁוּק שֶׁל זוֹנוֹת, אֶלָּא אָמְרוּ אָחִינוּ
יוֹסֵף יְפֵה תֹאַר וִיפֵה מַרְאֶה, שֶׁמָּא בְּקֻבָּה הוּא. וְתָפְשׂוּ
אוֹתָן וֶהֱבִיאוּם לִפְנֵי יוֹסֵף.
Immediately [upon the brothers’ arrival to Mitzraim through separate gates], Yosef said to [the gatekeepers], “Close the granaries and leave just one open.” He gave [the brothers’] names to the watched of [that] granary and said to him, “See to it that when these men come to your hand, grab them and bring them before me.” Three days passed, and they did not come. Immediately, Yosef took seventy strong men from the palace and sent them out on their behalf to find them in the marketplace. They went and found them in the marketplace of harlots - and what good was there in the marketplace of harlots? Rather, they said, “our brother Yosef is a handsome man; maybe he is in a stall” - and they grabbed them and brought them before Yosef.
Here’s the crux of your question, I think: why didn’t they seek him out sooner? You can’t say that the Parsha of Yehudah in fact happened later, because it explicitly says that it happened “at that time.” While the Midrash doesn’t quote that the brothers regretted their decision until the one cited above, Rashi does indeed bring down both teachings; you could say it’s a dispute amongst Midrashim, but you can’t say that Rashi is arguing on himself.
I can think of two answers to this; I haven’t seen anyone address the question at all.
The first answer lies in a careful reading of these two sources. The Rashi you cite says that “had you told us to return him, we would have obeyed you.” He doesn’t say anything about regretting their decision - for all we know, they still felt that they were correct. But the fact that Yaakov’s pain was so much worse than they anticipated - that was reason to demote Yehudah, for that part, at least, was not right. Even when one feels that he’s doing the right thing, he can’t harm someone who did nothing wrong.
However, as time went on, the brothers began to see a fuller picture, until they finally longed for an opportunity to rescue their brother - they finally regretted their sin.
This doesn’t fully answer the question, though, as they still should have gone down immediately when they fully regretted it, rather than long for an opportunity; to that I present answer number two: the brothers didn’t want to torment Yaakov any more than they already did. Yaakov thinks Yosef is dead, and the brothers see that he’s inconsolable. What should they say now?
“Hey, Dad, we’re going to Mitzraim for the week. Don’t worry about us.”
“Oh, okay. What’s the occasion?”
“Um... Yosef’s not dead? We actually sold him to Mitzraim?”
“Are you nuts?! I’ve been sitting here crying all this time - because you told me that Yosef was dead - and all this time you knew that he was still alive?!”
Whether Yaakov would have actually reacted this way or not there’s no way to tell, but perhaps the brothers were concerned for that possibility.