Would flying below FL285 be feasible for aircraft that don't comply with EASA CPDLC? I am not a pilot, my understanding about flight is limited. 
EASA CPDLC will require airplanes to be capable of PM-CPDLC data communication to fly above FL285. 

For an airline with multiple 767-300 and 757-200 airplanes, would it be feasible to consider the option of flying below FL285 in European airspace, instead of ceasing operation in the region or investing millions of dollars for avionics upgrades?
Unlikely. The extra fuel burned would cost a lot more than the required Avionics upgrade. 

Both the 75/767 would be well below optimum cruise level.