HP Ink Tank Wireless 415 - Wireless printing not working.

[TopComp]

Hello!
I am having problems with my HP Ink Tan Wireless 415 printer. When I try to print something, the print "starts printing" (the paper is "moved" down into the printer), it print's like 10% of the document INSANELY slowly, then it gets stuck, and after some time it fails. The other option that happens is that it won't even start printing and fails right after I press "print" button ("Couldn't print [filename]" error appears). "Error - Printing [filename] appears in Print Quee.

This only happens when I try to print something using Wireless Connection (everything works fine when using USB cable, or when I "scan & print" something directly in the printer without using PC, Scanning wirelessly works fine on every device).

(My wifi's encryption is WPA2-Personal.)

UPDATE:
Now, when I try to print something, it says in the printer menu that "it's printing", but the printer doesn't even move.

I have already:

• Unplugged and replugged the printer.
• Checked if Wireless Function is turned on in the printer.
• Installed and tested HP Printer Doctor (it didn't find / fix anything).
• Reinstalled drivers for the printer (multiple times).
• Put the printer to factory settings & reset Wireless Settings.
• Setup wireless through HP Smart & through Printer's embed server wizzard.
• Deactivated all antiviruses.
• Printed Wireless Info Page (it says that it's connected to my wifi, and it's working).
• Restarted printing service in Services.
• Checked for drivers / printer's software updates.
• Checked my internet speed (Download 38 mbps /// upload 50 mbps /// ping 18)
• I tried to print from other devices (Windows 10, Windows 7, Android 6 and 7), but got same "could not print" result. However, when I used Linux, the printer worked perfectly, without a problem.

I really hope there is a way how to fix this.
Thanks!

-Adam