Jenka's Puppies Locations
Next to the bed inside the Sand Zone Residence where Curly is. Note that you have to talk to the Mimiga on the very left of the room (by the table) before you can pick it up.
In the end of a long paw print-marked secret passage corridor close to Jenka's house an just below the two moving blocks that were dispelled after the fight with Omega.
In the bottom half of Sand Zone. Jump along the ledges with the *Parrots/Skulls* and eventually you will come to a small alcove with a secret paw print mark. Go through and make your way over to the house that the puppy runs inside and enter. Once inside you will see the puppy to the right of the screen. Jump up from the left-side of the table and step right and you should land on an invisible platform. Align your position with that of the table below you and jump up from here and head left, the jump up and head right and you will get to the puppy.
In the bottom of half of Sand Zone. Run along the lower sand area and as you approach the end you will see the puppy. He will start running so you will need to time your grab as he runs by you.
Sleeping on the ledge next to the red flower storage at the end the bottom half of Sand Zone. However... if you are playing the Switch port of Cave Story+ then this puppy will instead be located near the save point prior to the Omega boss fight.