<?php

$input = 'к';

$data = array('Москва', 'Балашиха', 'Химки', 'Подольск', 'Королев', 'Электросталь', 'Коломна');

$input = mb_strtolower($input);
$result = array_filter($data, function ($item) use ($input) {
	if (mb_stripos(mb_strtolower($item), $input) === 0) {
		return true;
	}
	return false;
});

echo '<ul>';
echo '<li>' . implode( '</li><li>', $result) . '</li>';
echo '</ul>';