After defeating Everdred (or not) you learn that Paula was last seen in Peaceful Rest Valley.
Visit Apple Kid
Before you go to Peaceful Rest Valley, buy a Ketchup Packet in Burlin Park if you don't have one, then visit Apple Kid. Give him the Ketchup Packet (or some other food if you prefer, but it makes no difference), then agree to give him some money. You need to give him the money to continue, so if you don't have it, fight enemies until there is enough in the ATM. After you give Apple Kid some food and money, his mouse will block the door. Talk to the mouse to get the Receiver Phone. This phone will allow people to call you no matter where you are. You can't make calls with it, though.
Before leaving Apple Kid's house, open the trash can to get a Broken Machine. You can't use this now, but it will be useful later. You can call Escargo Express to store it for now.
Go to Peaceful Rest Valley
Go toward the east side of Twoson. On the way there, you will find a pizza place. Go inside and talk to the girl behind the counter. She will tell you the number for ordering pizza. This will allow you to call Mach Pizza and order a pizza for delivery. The pizza guy will be able to find you no matter where you are, except in a few locations that he can't reach.
Keep going east, past the bus station, and you will find a path to a cave. Before the cave, there is an area of the trees where a Magic Butterfly often appears. Try walking around the trees to find the area that generates a Magic Butterfly.
You might encounter Ramblin' Evil Mushrooms and Mobile Sprouts inside of the cave. You will meet a girl after the cave who will buy the mushroom from you if you get Mashroomized. In Peaceful Rest Valley, go north. You will eventually reach a metallic pencil statue (or an octopus in the Japanese version) that blocks your path. You can check on it if you want to, but it won't make the statue go away. You have no choice but to go back to Twoson.
Get the Pencil Eraser
Back in Twoson, Apple Kid will call you and ask you to meet him right away. Apple Kid is in Burglin Park. Find Apple Kid near the lady selling bananas. Apple Kid will give you the Pencil Eraser, which makes all pencil-shaped objects in the vicinity disappear. Take the Pencil Eraser to the pencil statue in Peaceful Rest Valley and use the Pencil Eraser to get rid of the statue.
After you get rid of the statue, go north. If you want the photographer to take your picture, go north past the bridge and walk along the riverbank. Then after you get your picture taken, go back to the bridge. After you cross that bridge, the path will be straightforward until you reach a slope, where you can go north or south. There is a Travel Charm to the north. After that, go south to find a Luck Capsule. Then go north until you can go west. After going west down the slope, go south.
After you go past the broken bridge, go southwest to find a Croissant. Then go southeast, past a slope, to find a Bomb. From there, go west past the slope, then northeast to find a bridge. Cross the bridge and go north.
Eventually, the path will split into northwest and northeast. First, go northwest to find a Hardhat. Then go back the way you came and go southeast from the boulder. You will eventually see a cave opening to the southeast, but before you go in, go southwest on the slope to find a Cup of Lifenoodles. Then go back to the cave entrance and go in.