Можно ли выбрасывать исключение в предикатах?
Держащий в руке молоток видит только гвозди
Это про вас. Предикат обязан возвращать true/false. Эксепшены нужны для того чтобы отлавливать ошибки и передавать из вверх по стеку.
Пример из жизни: на вопрос есть ли пирожки продавец или говорит да или разворачивается и уходит
Рассматривать ситуацию как исключительную или нет - дело дизайна. Вы можете либо сделать предикат, но тогда эта штука долга возвращать true или  false и выкидывать исключения других ситуациях - например при нехватке памяти.
Либо сделать проверку и выкидывать исключение, но тогда незачем возвращать true - это будет уже не предикат.