Роман Томченко

line = $square[key[i]]
В строке key есть символы, которых нет ни в $square, ни в константе LINE, в итоге на одной из итераций переменная line равна nil

Тут у вас две ошибки:
1. Collections.rotate(tmp, 1); // тут, видимо, должна быть i, вместо единички. Так у вас i инкрементируется, но нигде не используется.
2. LinkedList tmp = new LinkedList<>(line); // Вы правильно догадались сделать копию исходного листа, но вам нужно его создавать каждый раз внутри цикла. В вашей реализации в все Value результируещей Map всегда попадает один и тот же объект (потому что ссылка одна и та же), он итерируется, и, в итоге, проходит полный круг.
3*. Я не уверен, но, кажется, нужно сдвигать в другую сторону.

Итого, метод получится такой:

private static void buildSquare() {
        int i = 0;
        for(Character elem: line) {
            LinkedList<Character> tmp = new LinkedList<>(line);
            Collections.rotate(tmp, i++); // i инкрементируется сразу в месте использования. (Попробуйте i--, так, кажется, будет правильнее)
            square.put(elem, tmp);
        }
    }