How to allow users to edit the profile of users in the same department? Department is a term reference or a list (text) field of the user entity. I want to let managers edit the profiles of users in the same department as the manager. 

I know I should define a custom permission, but in which hook should I check this custom permission?
In Drupal 7 if you want to change the access check for any path you need to use hook_menu_alter.

After you change the access callback you can write your own code which does the check you want.

You just need to be careful so you don't override access callback with a bad check. 

What I suggest here is to keep the original function which does the access callback user_edit_access check in your custom callback function.

I wrote sample code which gives you an idea which direction to go:

/**
 * Implements hook_permission().
 */
function example_permission() {
  return array(
    'edit own department users' =&gt; array(
      'title' =&gt; t('Edit own department users'),
      'description' =&gt; t('Allowed department manager to edit own department users.'),
    ),
  );
}

/**
 * Implements hook_menu_alter().
 */
function example_menu_alter(&amp;$items) {
  $items['user/%user/edit']['access callback'] = 'example_custom_user_edit_access';
}

/**
 * Custom access callback for user account editing.
 */
function example_custom_user_edit_access($account) {
  if (user_access('edit own department users')) {
    // We perform our check only for user with edit own department permissions.
    global $user;

    // Load user ( Department manager) via entity api.
    $user_wrapper = entity_metadata_wrapper('user', $user);

    // Get array of managed department terms id.
    $user_departments = $user_wrapper-&gt;field_user_department_managed-&gt;value();

    // Load user (Editor) via entity api.
    $account_wrapper = entity_metadata_wrapper('user', $account);
    // Get array of department belongs to terms id.
    $account_departments = $account_wrapper-&gt;field_user_department_belongs-&gt;value();

    // Check any common term id.
    $common_departments = array_intersect($user_departments, $account_departments);

    return !empty($common_departments);
  }
  // For other user we perform default check.
  return user_edit_access($account);
}