Which permission is associated with variable_set()? It seems that only site administrators can use variable_set(). If this is truly the case, is there a special permission that grants variable_set() function to site administrators?
There is no permission associated to using variable_set(). Permissions are associated to pages, and not having a specific permission doesn't allow to see those pages; associated to part of the page, and not having a specific permission doesn't allow to see that specific part of the page; or associated to an action, and not having a specific permission doesn't allow to do/start that action. 

There could be a module that checks the currently logged-in user has a permission before saving some data with variable_set(), but that doesn't mean every call to variable_set() needs the user to have a specific permission. variable_set() doesn't even check for any user permission.

As for what done from Drupal core and its modules, none of the functions calling variable_set() that aren't part of tests use code similar to the following PHP pseudo-code.

if (user_access($permission)) {
  variable_set($key, $value);
}


This means that, for example, in a form submission handler for a setting page used by Drupal core, the settings will be saved independently from the user permissions the logged-in user has. That user has the permission to see that setting page, though.
If you are noticing that setting values for a form are saved just when the user is administrator, and that happens also for setting pages handled by Drupal core modules, then there is something wrong happening.