Are you sure that this printer has the capability of A4? Most printers have letter size. Just because it has A4 in the menu does not mean that it has this capability, It could be a common menu used across a platform of printers. The manual should verify this.
One thing you can try is to reset everything by unplugging the printer and the re-plugging it.
What does HP support have to say to this?