I had experienced this same situation. One user in an AD group with Full Control would get an "Access Denied" error when adding a "Link to a Document", but could perform all other full control tasks such as adding folders, setting permissions, etc. All others in the same AD group and with the same permissions could "Link to a Document".
TLDR: Master page was checked out; checking it in, re-publishing it, and approving it fixed the problem.
Troubleshooting:
Comparing this user's access to others in the same AD group that was granted full access, the permissions were the same.
Looking at the permissions from the top of the site down, everything seemed to be in order. Checking permissions for the user, everything checked out okay (note: we follow grant not deny access methods so there was nothing denying access anywhere).
Following the advice in Arko D's post, I checked the Master Page and found it was checked out. I checked it back in, re-published, and approved it. This corrected the issue.
I'm still not sure why only one user experienced this issue, while all others in the same groups and with the same permissions had no trouble at all, but it may have something to do with when the page was checked out and the timing of when this user was added to the AD group or when the AD group was granted Full Control.