Stai confondendo un po' di cose.
Un ArrayList<String> è una lista di oggetti String. Gli oggetti String sono, per loro natura, immutabili: non si modificano dopo la loro creazione.
Il metodo replace() della classe String (come qualunque altro metodo di "modifica"), in pratica non modifica nulla: crea e restituisce un nuovo oggetto String che rappresenta l'oggetto di partenza modificato... ma l'oggetto di partenza non subisce alcuna modifica, perchè, come già detto, gli oggetti String non sono modificabili (sono immutabili).
codice:
// Esempio
String s1 = "CULLA";
String s2 = s1.replace('U', 'O');
System.out.println( s1 ); // Stamperà CULLA
System.out.println( s2 ); // Stamperà COLLA
Ora, il metodo contains() che stai usando è quello della classe ArrayList. Tale metodo restituisce true se l'oggetto passato è contenuto nell'ArrayList.
codice:
ArrayList<String> lista = new ArrayList<String>();
lista.add("CULLA");
lista.add("COLLA");
System.out.println( lista.contains("CULLA") ); // Stamperà true
System.out.println( lista.contains("L") ); // Stamperà false
Tu gli stai passando un carattere (o, non meglio specificato, oggetto carattereMenu). Dato che stai lavorando su un ArrayList di oggetti String, il metodo contains() si aspetta un oggetto String (e non un carattere, a meno che la stringa non sia composta da un solo carattere, ma si tratta comunque di un oggetto String di lunghezza 1) e restituisce true se la stringa passata è contenuta nell'ArrayList...
Insomma... stai facendo una grandissima confusione.
Spiega cosa hai in mano (come strutture dati), cosa vuoi fare (che elaborazione) e come intendi procedere per ottenerlo perchè non si è capito molto.
Ciao.