You are correct. Creating representations that vary based on user permission is not particularly cache friendly. Is it possible to classify permission variants into just a few categories? e.g. resource-low-security, resource-medium-security resource-high-security
Sometimes this approach is possible, sometimes it is not. The other aspect to consider is whether caching is critical for this particular resource. Maybe it is now?
Also, it is not necessary to wait until the user clicks on a link to find out if the user has the permissions to follow it. The client could perform an OPTIONS request on links in the background to discover which links are available and dynamically disable the links that are not accessible.
There is no single answer to this problem. Different solutions will work in different cases depending on the requirements.