Payment Page not accessible to anonymous users in Wordpress
Since you have questions regarding the specific steps you took, I copy and paste all of them below and intersperse with my responses (IN BOLD CAPS for clarity):


I set up a CiviCRM Membership and a Price Set for the membership > GOOD
I created a profile (including custom fields) for the membership registration > GOOD
I ticked the box that says 'Account Creation Required' under WordPress user account registration option for the profile > YOU MUST INCLUDE A PRIMARY EMAIL ADDRESS FIELD IN THE PROFILE FOR THIS FEATURE TO FUNCTION PROPERLY
I've set up a CiviCRM Payment Page for membership fees using above profile. > GOOD
I've checked the permissions for Anonymous Users to create, edit, view profiles...> AS INDICATED HERE, YOU ALSO NEED TO ENABLE THE PERMISSION FOR
PROFILE LISTINGS AND FORMS
...and Access all custom data fields (Not sure this is necessary?) > YES, THIS TOO IS NECESSARY
CiviCRM: access contact reference fields is checked for Anonymous users > UNLESS YOU ARE USING CONTACT REFERENCE FIELDS IN YOUR PROFILE, THIS IS NOT NECESSARY
CiviCRM: add contributions of type Campaign Contribution is checked for Anonymous users > UNLESS YOU ARE USING THE FINANCIAL TYPE OF CAMPAIGN CONTRIBUTION FOR MEMBERSHIP DUES, THIS IS NOT NECESSARY
CiviContribute: make online contributions is checked for Anonymous user > GOOD
CiviCRM: access Contact Dashboard is checked for Anonymous user (not sure if necessary?) > AS INDICATED HERE, THIS PERMISSION SHOULD NOT BE GIVEN TO ANONYMOUS USER
I've created a Wordpress page and used the CiviCRM shortcode to add the payment page > IF YOU HAVE ALL OF THE REQUIRED FIELDS IN PLACE PERMISSIONS ENABLED AND THIS STILL ISN'T WORKING FOR YOU, PERHAPS YOU SHOULD TRY USING ONE OF THE OTHER OPTIONS FOR LINKING YOUR MEMBERSHIP PAGE TO YOUR WEBSITE AS INDICATED HERE


Hope this helps!
Tamar