I was trying to Edit a document -which hosted on SharePoint- in client side Word application , but I faced this error "Sorry, We couldn't find your file. is it possible it was moved, renamed or deleted? " followed by half of the URL.
After alot of trails I found the best ways to solve this issue, as it was not clear in most of the websites.
You have to check the client side, as my problem was there, my Microsoft Office edition didn't allow me to open the file, Try to Repair it , or better to UnInstall then Install it again
$config = (Get-SPSecurityTokenServiceConfig) $config.Update()
Also you can find more in the following links: