This sounds a bit strange. The point of the permission system is that content without access wouldn’t appear at all, so clicking on it and receiving an error shouldn’t even happen.
Not that I have anything against the request to have category specific error messages.
One option to consider would be to use field permissions instead of category permissions. That’s what I use in my Typography.Guru Academy section, which shows and limits content access based on three member groups (guest/normal member/paying member). Even as guest you will be able to access EVERY record, but the course content (an editor field) might be hidden because of your member group. But in the end, for a good custom solution, it usually requires some custom Pages templates.