Non sono pratico di dom ma se ti puo' servire come idea iniziale..
Codice PHP:
//$parola = '*par';
foreach($xml as $citta){
    if(
substr($parola,0,1) == '*'){
        if(
substr($parola,-3,3) == 'par'){echo "citta finisce per parola chiave";};
    }elseif(
substr($parola,-1) == '*'){ 
        if(
substr($parola,0,3) == 'par'){echo "citta inizia per "$parola;};
    }elseif(
eregi('*',$parola)){
        if(
eregi($parola,$citta)){echo "citta contiene "$parola;};
    }

meglio con un espressione regolare .