Not a 10k+ user here, but we had a similar situation on another site where I do have 10k+ reputation. As I answered there, this happens because one of the "safeguards" that are implemented in the system to prevent spammers from exploiting deleted spam posts is acting a little overzealous.
These "safeguards" include removing the title from the URL, suppressing the "related questions" list that normally appears on the 404 page shown to <10k users, and annotating the deletion notice with "this question was deleted as spam or offensive". (Note that the criteria for the "spam mask" is completely different, as it's a completely different mechanism - that only checks for helpful spam flags, not if the post was actually deleted as spam or abuse.)
It's that first part that's the issue: the pagination and sort links consist of full-form URLs that contain the title, and since the system considers everything that comes after the post ID as being part of the title, query commands like ?page=2
get stripped out as well, preventing page links from advancing.
As DavidG commented, manually removing the post title from the URL prevents the title stripping logic from taking place, and as such the query command doesn't get stripped out and works normally. (I suggest reading my answer I linked above for a full, technical explanation of how it works.)
As far as this "popular" post being supposedly deleted as spam or abuse: this is because the system, when checking to see if the "safeguards" should kick in, uses a very simple check: if the post is deleted, locked, and has helpful spam or abuse flags, they kick in. All of these happen automatically when the post is deleted as spam or offensive, but as you can see, it's possible for this circumstance to be arranged manually. This may be what happened in this case, and is definitely the case if the deletion and lock weren't attributed to the Community user.
TL;DR: It's a bunch of rare edge cases coming together to bite. Thankfully, the latest development version of the SOUP user script contains a (partial) fix for this issue.
press 2
meant the actual key on the keyboard but I see it's actually about clicking the link to page 2. I feel a red circle could have made that even clearer.