バイト先の店長に辞めると言いづらいです

一ヶ月働いてＯＫをもらっているのであれば

今のバイトに一ヶ月入って辞めればいいです。
今、いいましょう。

他の方たちがおっしゃっていることは正論ではあると思いますが、
辞めると言われた側にも、今日、明日、その後があるわけです。
一人がやめるということは、一人求人を出さなくてはいけません。
求人を出すのに、費用、時間、適任者が現れるか否かの手間暇が
あなたが辞めるせいでかかってしまいます。
その間、誰かがあなたの穴を埋めることになったとしても、
迷惑がかかっています。
一ヶ月はそれらをするために必要な期間なのです。

今までの職場に対して、正社員になったからといって
いきなり辞めるのは、礼儀というかモラルに欠けます。
辞めるからには、一ヶ月前から報告というけじめをつけてから
辞めるべきです。
正社員になるわけですから、礼儀の基礎はやってから
新職場にいくべきです。

期間の定めのあるアルバイトは　原則として辞められませんが、そうでないなら大丈夫です。

でも、辞める時は　他社に勤めるからとは言わず　体調不良とか適当な理由をつけるものです。正直すぎます。
まあ、次の就職先の入社日の少し前まで勤めるということで折り合うしかありません。

働く期間を契約で特別に決めていない場合には、２週間前までに意思表示をすれば退職できることが法律で定められています。

具体的には「退職します」と２週間前までに言えばよいのです。
断わられそうな場合には、退職届という書面にして提出してください。
これは、民法 第627条 に規定されています。
https://ja.wikibooks.org/wiki/%E6%B0%91%E6%B3%95 …
[ 民法 ]
（期間の定めのない雇用の解約の申入れ）
第六百二十七条
当事者が雇用の期間を定めなかったときは、各当事者は、いつでも解約の申入れをすることができる。この場合において、雇用は、解約の申入れの日から二週間を経過することによって終了する。

最低でも一ヶ月は働いてもらう、という契約をしていたのなら、その間は働かなければなりませんが、あなたが知らなかったなら契約していることにはなりません。
後から「最低1ヶ月前には報告してもらわないと困る」と言われても、そんなことは通用しないのです。
ただ、１ヶ月は働けるということのようですから、そうすれば良いでしょう。
十分譲歩したことになるので、その後は堂々と辞めてください。
一ヶ月の間に新しい人を探せなければ、それは店側の問題であってあなたには何の責任もありません。
因みに、上記第六百二十七条 に続けて、民法は次のような規定も設けています。

（やむを得ない事由による雇用の解除）
第六百二十八条 　当事者が雇用の期間を定めた場合であっても、やむを得ない事由があるときは、各当事者は、直ちに契約の解除をすることができる。

つまり、仮に「最低でも一ヶ月は働いてもらう」という契約が為されていたとしても、あなたに「やむを得ない事由」がある場合には辞めることができる、ということです。
正社員になれる、というのは「やむを得ない事由」として立派に通用するでしょう。
いずれにせよ、法律の後ろ盾がありますので、堂々と退職できます。
大事な正社員の職を失わないように、しっかりと腹を決めましょう。
変な仏心は起こさず、当初の目的を完遂してください。
強引に引き止められたら労働基準監督署に相談してください。
http://www.mhlw.go.jp/stf/seisakunitsuite/bunya/ …

なぜバイト先に許可を取るのかが理解できない。

「イヤ」と言われるのは当たり前だし、「じゃあ正社員を蹴った分の補償はしてくれるのか」と言えばそんな義理ないと言われるだろう。バイトを辞めるのに理由なんていらない。1ヶ月前に言えば正当な権利として進められる。
「君が辞める損害を補填してくれ」と言われたら、「裁判で闘います」と言う覚悟で。

おじさんです。

「明日バイトがあるので店長に辞めさせて欲しいと言わなければいけないのですが、どう言ったらいいのか…とても言いづらいです」
→まだ20歳の若い女性あれば、その店長には云い難いでしょうね。
そもそも、アルバイトの退職は会社側(店長)に了解をもらう必要はないのです。
ですから、「何日をもってアルバイトを辞めさせていただきます」といえば、それでいいのです。
その時の店長の反論を聞く必要はないのですよ。
店長が話しの分る人であれば話し合いをしてもいいのですが、そうでないとすれば話し合いは必要ありません。
それで法的には何も問題はありません。
もっと、極端に言えば、翌日からアルバイトに行かなければいいのです。
話しをしたくないのであれば、便箋1枚に退職届を書いて送付してもいいのですよ。

一か月、気まずいかも知れませんが　怒るタイプの店長だと、嫌みを言われたり、嫌な仕事を回されたりは　覚悟が必要かもしれませんね。

何もない事を願いますが。
今の人が多めに出るのが無理ならとりあえず、早く次の人が見つかるといいですね。４日間も悩まれたんですね。質問者さんはとても真面目で信頼される方だと思います。新しいお仕事楽しみですね、頑張ってください。

正社員になれるのは魅力ですよね。

採用までされて断ることないと思いますよ。
初めからバイト先では止める時１ケ月前にと規約があったのでしょうか？
職安の方はプロだし、多くの人を見てこられています。正論だと思います。
質問者さんが優しく、お願いするような姿勢だったので　店長さんは強気に出られたように思います。
「どうしても就きたい仕事なので申し訳ありませんが、直ぐにやめさせてください」と梃子でも動かない様子を見せるべきですね。
法律的に問題になるのかは職安の方に相談されてはいかがでしょうか？多分大丈夫なはず。
店長さんも急で驚かれたんでしょうね。納得してくれることを願っています。