Why do the databases go into the "recovery pending" state when the share permissions are changed from "everyone"?
It sounds like a simple permissions issue. 

Why did this happen? 

The Everyone permission literally allows anyone to connect to those network shares and access those files. When you remove those permissions, now no one is allowed to access them. What may be confusing is that you may think that SQL Server has access to those files and shares, when, in fact, it does not.

To allow specific access to those databases that run over SMB shares (starting with Microsoft SQL Server 2012), Microsoft recommends that the SQL Server service run as a &lt;domain name&gt;\&lt;user name&gt; and that this account have FULL CONTROL to the file share AND NTFS permissions to the underlying files and/or directories within that file share.

Alternately, Microsoft recommends that if you use a system account instead for the SQL Server service account then apply FULL CONTROL share AND NTFS permissions to the account &lt;domain_name&gt;\&lt;computer_name&gt;$--where computer name is the computer name of your SQL Server.

I'd retry removing those "everyone" permissions once more, in a test environment, to validate that this fixes your issue.

For more details see:

https://msdn.microsoft.com/en-us/library/hh759341.aspx