Question about Vbe and operation regions of BJT
Is there a chance that the change in the base voltage will decrease Vbe and force the transistor into the cut-off region? 


Yes this is possible, and it would result in non-linear operation of your amplifier.


  Is there any chance this might happen before first entering the saturation region?


Yes it's possible to (mis-)design an amplifier so this happens.


  when deciding on the swing of the output voltage are we more worried about entering saturation or cut-off region?


You need to consider both when designing your amplifier. 

Assuming we're talking about a common emitter amplifier, you need to be sure the amplifier can handle the complete range of input amplitudes desired without going into cut-off, and you need to be sure it can handle the complete range of output amplitudes without entering saturation.