The earliest Pastoria City is accessible is after you have 3 Gym Badges in Platinum.
After defeating Fantina, head to the east of Hearthome City and battle your rival. Then progress to Solaceon Town and farther progress to Veilstone City. There are a few trainers on this route that can cause a minor challenge, namely the last double battle against 2 Ace Trainers. From here, challenging Maylene’s Gym is not essential to gain access to Pastoria. Head south of Veilstone City until you reach Valor Lakefront, and then head west until you reach Pastoria City! The Move Relearner is the Collector in the house near the lake.
Note: you may wish to check that your Pokemon doesn’t learn the move you desire at a near level - Platinum has many instances of Pokemon learning their best moves through the Move Relearner so it is best to save Heart Scales for when you actually need them.
