Is it possible to change this message
Sorry this site is not shared with you
to something else when users don't have permissions?
If you are talking about the
AccessDenied.aspx page, then no. The text on the page is retrieved from resource files.
Unless you physically alter the page in the 15 hive on your web front-ends - which is possible, but not recommended and they can be overwritten by CU's etc.
It is recommended not to modify the OOB things or content. I would say to go with your custom access denied page. To do this, in SP2013 we have a bug and can achieve using HTTPModule. Please look into the following URL for more details.
Please let me know if you have any queries.