Как вывести нужные строки через grep?
У меня ощущение, что вывод получен SQL-запросом. Если так - то и фильтрацию надо делать SQL-запросом, а не извращаться с grep'ом - ибо grep вынужден парсить поля заново.

Второй вариант - работать чем-то типа AWK, который разбивает строки на поля. Правда, там м.б. проблемы при пустых полях, которые он не увидит.

1) "Зарплата от 1000 и выше" = "четыре или более цифры" = [0-9]{4,} или точнее [1-9][0-9]{3,}

2) Отрицание в regex пишется так:
[^K] - любой символ, кроме "K"
[^KJ] - любой символ, кроме "K" и "J"
[^K-P] - любой символ, кроме диапазона {от "K" до "P"}

3) Если Вам надо работать именно с полями - то, как я уже сказал, grep работает очень плохо. Вариант 'PAUL.+BOSTON' от mureevms плох тем, что сработает, если эти значения появятся в поле "фамилия", а они это могут.
Хуже того: этот вариант примет и имя "COPAULER" (придумал из пальца, чисто для примера).

Я могу напрячься и написать более корректный regex на это дело - ну, для начала огородить эти слова пробелами. Но не буду, ибо лень.
1. 1000 - это 4 символа. Все, что меньше 1000 - 1,2 или 3 символа. Известно, что зп это последняя строка, поэтому ищутся стоящие подряд от 4-х цифр от конца строки:
grep -E '\s([0-9]{4,})$'
2. Выборка по K или J и реверс вывода
grep -E -v '(\sK\s|\sJ\s)'
3. Поиск имени и города в одной строке:
grep -E 'PAUL.+BOSTON'