Regarding שִׁיר הַמַּעֲלוֹת:
the Mishna Brerua 267:1 connects it to Tachanun, so that even on Erev Shabbat afer Mincha-time (1/2 hour afternoon) on already replaces עַל נַהֲרוֹת בָּבֶל with שִׁיר הַמַּעֲלוֹתת.
א) אין נופלין - מפני שהוא סמוך להכנסת שבת כ"כ הלבוש וכתב הפמ"ג ונראה דה"ה כשמתפללים מנחה גדולה אחר חצות נמי אין נופלים ע"פ וכן מי שאוכל פת אחר חצות ג"כ אין לומר על נהרות בבל כ"א שיר המעלות ועיין בה"ל:
Regarding Migdol/Magdil:
The earliest source I found is the Darchei Moshe on Orach Chaim 189:1 quoting the Abudraham who says that we say Migdol on Shabbath, Magdil during the week. he doesn't say what to do on Chag.
בהגהות אלפסי החדשים במרדכי דברכות מצאתי שאין לומר שבכל יום מטיב לנו אלא בכל יום ונכון הוא דלא יהא נתינת טעם למה שלמעלה ממנו שאמר המלך הטוב כו' במרדכי סוף ברכות כשמסיים לא יאמר ונאמר אמן אלא ואמרו אמן עכ"ל וכתב אבודרהם קבלתי מרבותי שבשבת י"ל מגדול ישועות מלכו בוי"ו ובחול מגדיל ביו"ד ונ"ל הטעם כי בשבת הוא מלך גדול נגד החול ומגדול מלא בוי"ו או החולם נקרא מלך גדול ומגדיל חסר יו"ד וחירק הוא מלך קטן ועוד מגדיל הוא בתהילים ועדיין לא מלך דוד ומגדול היא בנביאים וכבר היה מלך עד כאן לשונו:
The Drishsa says the same thing.
A more detailed set on instructions you'll find in the Kaf haChaim O:C 189:11 who elaborates on the Abudraham:
יא) קבלתי מרבותי כי בשבת אומר מגדול. ונ"ל הטעם כי בשבת הוא מלך גדול כנגד החול ומגדול מלא בוא"ו וחולם בוא"ו הוא מלך גדול. ומגדיל היא חסר יו"ד בחירי"ק בלא יוד היא מלך קטן. ועוד מגדיל הוא בתהלים ועדיין לא היה מלך ומגדול הוא בנביאים וכבר היה מלך. הרד"א. והביאו ד"מ אות א' כנה"ג בהגה"ט. וכתב שם הכנה"ג ולפ"ד אין לומר מגדול כ"א בשבת או ביו"ט אבל בר"ח אומרים מגדיל אבל מנהגינו לומר מגדול אפילו בר"ח והטעם שמעתי חדש ושבת קרא מקרא עכ"ד. וכ"כ העו"ת אות א' מ"א שם. וי"א שגם בסעודת מוצאי שבת אומרים מגדול. ואני שמעתי משם מהרד"פ ז"ל שגם בסעודת מילה ע"פ הסוד ראוי לומר מגדול. חס"ל אות ח' ובס' כ"מ כ"י איתא שגם בסעודת פורים יאמר מגדול בשביל אותה הארה המתגלית ביום ההוא. בן א"ח פ' חקת אות י"ט ולפ"ז נראה שגם בסעודת חתן או סיום מסכתא י"ל מגדול כיון שיש הארה של מצוה ועיין לעיל סימן קפ"ז:&rklm;
He adds Yom Tov to the list of Migdol. Some add Rosh Chodesh to the list. Some add Melave Malka, Some add the meal at a Brit Mila, some add the Seudat Chattan (Wedding? Sheva Brachot?) and a Siyum.
In 187:4 the Kaf haChaim says to say Migdol on Shabbat, Yom Tov, Rosh Chodesh, Brit Mila, Wedding, Purim and Siyum:
ד) בשבת ויו"ט ור"ח ומו"ש ומילה וחתונה ופורים וסיום מסכתא אומר מגדול כמ"ש לקמן סי' קפ"ט אות י"א יעו"ש:
The Ateret Zekeinim says to say Migdol on Shabbat and Rosh Chodesh.
וי"א בשבת מגדול בוא"ו ובחול מגדיל ביו"ד (ד"מ) ואני קבלתי שגם בר"ח י"ל מגדול בוי"ו וסי' חודש ושבת קרא מקרא ר"ל כמו שכתוב בנביאים ע"כ:
The Mishna Berura says the custom is to say Migdol on Shabbat, Yom Tov and Rosh Chodesh.
נוהגים לומר בשבת ויו"ט ור"ח מגדול ובחול מגדיל ויתר דקדוקים שבנוסח בהמ"ז עיין בא"ר סימן קפ"ז שהאריך בזה:
I once heard that the reason we switch Magfil with Migdol is because מַגְדִּיל is in Tehillim (18:51) which is part of Kesuvim - and there wan ancient Takana not to learn Kesuvim on Shabbat (so that the people go to listen to the weekly Drasha instead of getting carried away with the fascinating stories in Kesuvim - see Shabbat 115a).
So we replace the Kesuvim verse with its parallel Nevi'im verse (Shmuel-II 22:51) - the only difference being that it's now מִגְדּוֹל instead of מַגְדִּיל - as a reminder of this.
Regarding Purim:
See above. שִׁיר הַמַּעֲלוֹת according to the Mishna Berura. מִגְדּוֹל according to the Kaf Hachaim.