Почему проверка на то что строка является палиндромом работает только с латинскими буквами

Потому что все символы, не входящие в [a-zA-Z_0-9], вы заменяете на "". Поэтому слово "машина" легко и непринуждённо становится палиндромом, ибо пустая строка равна сама себе после переворачивания.

Самый простой вариант - не делать данную замену:

public static boolean isPalindrome(String str)
{
    StringBuilder sb = new StringBuilder(str);
    String inversedStr = sb.reverse().toString();
    return inversedStr.equalsIgnoreCase(str);
}

И использование:

String str = "Тест";
if (isPalindrome(str))
    System.out.println("Палиндром");
else
    System.out.println("Не палиндром");

Вместо StringBuilder можно воспользоваться и обычным циклом:

public static boolean isPalindrome(String str)
{
    String lowerCaseStr = str.toLowerCase();
    int length = lowerCaseStr.length();
    for (int i = 0; i < length / 2; i++)
    {
        if (lowerCaseStr.charAt(i) != lowerCaseStr.charAt(length - i - 1))
            return false;
    }
    return true;
}

Если же обязательно нужно отфильтровывать неподходящие символы, то вместо \W можно воспользоваться перечислением допустимых символов:

String filteredStr = str.replaceAll("[^a-zA-Z_0-9а-яА-ЯёЁ]", "");

Отдельно стоит отметить, что если при использовании Scanner-а на любую строку из кириллицы код возвращает "Палиндром", то нужно задать кодировку, в которой Scanner будет считывать символы. У меня в консоли в NetBeans это, например, Windows-1251:

Scanner scanner = new Scanner(System.in, "windows-1251");