Drupal - How do I do a 'required if other field = x' using the entity validation api?

That sounds like a job for Drupal's Form API states.

Just add a hook_form_alter similar to this, in a custom module:

function MYMODULE_form_alter(&$form, \Drupal\Core\Form\FormStateInterface $form_state, $form_id) {
  if ($form_id == 'FORM_ID_TO_ALTER') {
    $form['OPTIONALLY_REQUIRED_FIELD']['#states'] = array(
      'visible' => array(
        ':input[name="CHECKBOX_NAME"]' => array('checked' => 'checked'),
      ),
      'required' => array(
        ':input[name="CHECKBOX_NAME"]' => array('checked' => 'checked'),
      ),
    );
  }
}

The form_alter() solution will only work when you're using a form to save the entity, so I believe that the answer is not the correct one. Here's how you do it with Drupal's Entity Validation API:

Create a constraint and add it to the entity type instead of adding it to a field. Ex:

## See hook_entity_type_alter().
function custom_validation_entity_type_alter(array &$entity_types) {
  if (isset($entity_types['node'])) {
    $entity_types['node']->addConstraint('ConstraintName');
  }
}

Next, in your ConstraintValidator::validate() method, you will get receive the entity as the first argument and you can perform the validation. Here's a code sample from the same article.