The Publish Search permission is needed to have the option to make a Saved Search Public. You can accomplish it by doing the following:
- Navigate to Users/Roles > Manage Roles.
- Click Edit beside the role in question.
- Navigate under Permissions subtab > Lists sublist.
- Add the Publish Search permission with Full access level.
- Click Save.