The document does not exist, it may have been deleted by someone else

I've run across this a time or two before. Not sure why it happens but the solution was to review the database tables and find where the problem was and manually remove the corrupt records. Although this is highly frowned upon, it was a last resort. You might also check the recycle bin to see if you can restore the document back before going to the database.

I have the same issue. I'm not sure how to access the database on my local machine. Could you point me in the right direction?

Just to add to this: It's worth checking the 'DocumentForeignKeyValue' value in the CMS_Document table.

We had this exact issue and the cause was the primary key for our custom doc type not matching the foreign key in the cms_document table.

Hope this helps someone!

I ran into this issue too and confirm that Distinction_Limited's solution helped me (Kentico9). I had to delete the related item(s) in the CMS_Attachments table, then in the CMS_Documents table. Thanks!