Drupal - How can I change the search form placeholder value?

You don't alter a TranslatableMarkup object: You replace it with another TranslatableMarkup object you obtain from t('The new placeholder') or new TranslatableMarkup('The new placeholder') (or a method returning a TranslatableMarkup object).

function mytheme_form_search_block_form_alter(&$form, FormStateInterface $form_state) {
  $form['keys']['#attributes']['title'] = t('The new placeholder');
}

The result of this code is the following (on Google Chrome running on OS X El Capitan).

What you are showing is not the placeholder, but the input title. To change the placeholder of a form element, you should use code similar to the following one.

function mytheme_form_search_block_form_alter(&$form, FormStateInterface $form_state) {
  $form['keys']['#attributes']['placeholder'] = t('The new placeholder');
}

Using this code, you get the following result.