Would flying below FL285 be feasible for aircraft that don't comply with EASA CPDLC?
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.