Google Docs Add-on only works for one account

I have deployed an Google Docs add-on but it only works for one account if there are multiple accounts in the browser. Specifically, it only works for the (default) Google account. Other accounts randomly show one of following errors

ScriptError: Action not allowed or

ScriptError: Authorization is required to perform that action

What should be done to avoid this, so that any accounts can use the add-on?

It has to do with the authorization mode. So the other accounts in the browser did not give proper permissions for the add-on. You need to edit the onOpen(e) to handle authorizations mode where the user didn't authorize the add-on yet. See example below:

 function onOpen(e) {
   var menu = SpreadsheetApp.getUi().createAddonMenu();
   if (e && e.authMode == ScriptApp.AuthMode.NONE) {
     // Add a normal menu item (works in all authorization modes).
     menu.addItem('Start workflow', 'startWorkflow');
   } else {
     // Add a menu item based on properties (doesn't work in AuthMode.NONE).
     var properties = PropertiesService.getDocumentProperties();
     var workflowStarted = properties.getProperty('workflowStarted');
     if (workflowStarted) {
       menu.addItem('Check workflow status', 'checkWorkflow');
     } else {
       menu.addItem('Start workflow', 'startWorkflow');
     }
     // Record analytics.
     UrlFetchApp.fetch('http://www.example.com/analytics?event=open');
   }
   menu.addToUi();
 }

Using the code below, the "default" account will see the option "Check workflow status", but the others will see only "Start workflow". Notice that your issue is not related with multiple accounts in the browser, but instead with multiple users in the same document.