Certainly the French do not use only square pillows - We have bought all our rectangular (feather and down) pillows locally here with no problem at all.
Alot of our French friends buy them and prefer them to square ones. Good bed linen ranges also carry pillowslips in both rectangular and square shapes.