It's been a very long time since I caught the Regi's...but based on those instructions, you're in a cave of some sort. You need to go through the left opening, then keep going left until you go through another opening. Then, head down and go through the bottom opening, and keep heading down to another opening. I assume beyond this is a rock you can use Rock Smash on.