As you may know storage drives will perform slower when they are full (Or close to). Although this rule holds up, if it takes longer than 5 seconds to move between menu items then something is really wrong here.
Often times hard drives can spit out warning when they are really old (Rolling on my g'ol friends at ltt).
Lets try this: Bring your ear close to the PS4 at these 3 stages
- Startup: When you turn on the PS4 if it is louder than the disc drive that would mean it's time for a new one
- Idle: When it's just sitting on the home screen is it obnoxiously loud? This is another sign that it needs replacement
- Loading the game in question (Please let me know ASAP): When loading up that game (And all the others) Is the hard drive spinning at really high RPM's? I wouldn't say that's hard drive replacement level.
- It is also a good idea to check if the fans are really loud at these three stages. This means it's overheating and thereby throttling. If this is the case then either: Replace the thermal paste or diagnose it to a component around the board.
Apart from that I don't really know as I am not a technician on PS4's. Someone who would be better fit to solve this would be @jayeff or @danj. I'll leave this with them as they are a lot more experienced at this.