Controlling a dependent field in a multi-instance paragraph
I managed to make it work using a different approach; instead of overriding the NodeFrom, I used hook_field_widget_WIDGET_TYPE_form_alter and edited the subform array there.
Example:

/**
 * Implements hook_field_widget_WIDGET_TYPE_form_alter().
 */
function MY_MODULE_field_widget_entity_reference_paragraphs_form_alter(&amp;$element, \Drupal\Core\Form\FormStateInterface $form_state, $context)
{
  //Logic to exclude other Paragraph types
  if ($element['#paragraph_type'] !== 'YOUR_PARAGRAPH_TYPE'){ //e.g. cities
    return;
  }
  $element['subform']['field_places']['#states'] = [
    'visible' => [
      [
        //It worked for me with the ID of the select, I think you can use the name also
        '#edit-field-cities-0-subform-field-city' => array('value' => 'Cairo'),
      ]
    ]
  ];
}

When I add another paragraph, the ajax is fired and the selection is still preserved.
I haven't tried with other Ajax fields present though.