I have completed my sims perfect fishing collection today, and I had by far the most trouble trying to get a Perfect Ninja Starfish. I have been googling, scouting this forum for old posts, and coming up with nothing but tips that don't work or use some mod that I don't want to add. To FISH for a Perfect Ninja Starfish you need Perfect Tofu and that isn't available anywhere. Also growing either of both on a Perfect Omni Plant doesn't give you a Perfect harvestable. I even read in one post about a person who spent 4 REAL days and a boatload of tofu before he got one!
Then I thought of something.... If you own Generations, and if your sim has a high enough Science skill, they have a chance of increasing the quality of whatever it is that they clone! So I had my sim create a batch of 8 samples from a Normal quality Ninja Starfish, and ended up with 7 successful clones, of which one was Perfect! So there you have it! I didn't want to post this tip in threads that are around 5 years old, due to necro posting, but if you want a Perfect Ninja Starfish, you have to clone it!
Edit: The only downside to this is then when you mouse over it it will be shown as 'store bought' and not 'caught by <sim>'. The alternative (though not mod-free) is to buy some tofu, and use Nraas DebugEnabler to change it's quality to perfect. If you go fishing with that the odds are big that you will catch a perfect Ninja Starfish.