Run this test. I suspect your autodiscover record is not set correctly.
Do you see the PF connection listed for Outlook 2013?
https://learn.microsoft.com/en-us/exchange/troubleshoot/public-folders/outlook-or-owa-cannot-connect-to-public-folders#run-an-autodiscover-test-for-affected-users
What is your autodiscover record set to? Office 365 or on-prem?
Are you in hybrid mode? OR all all mailboxes in Office 365?