First of all, welcome to the HDL arena. I personally don’t see much value in schematic-based design methodologies anymore since HDLs can accomplish the same thing (structural description) as well as behavioral description. HDLs also free you from proprietary netlist/file formats that may become useless if you don’t keep updated software.
That said, Verilog and VHDL are similar in many ways. Many experienced users tend toward VHDL because it has more features that are useful in some settings. I think learning Verilog is easier and less confusing from a syntax point of view and the later migration to VHDL is straightforward. Learning VHDL first involves a steeper curve.
I’ve never used Protel for FPGA design, only PCB design, so I can’t comment on that.
My suggestion is to start with Verilog and leave schematics behind. Teach yourself to visualize the behavior you want and learn how to describe it in HDL. Always remember that Verilog/VHDL are not software. They are hardware description languages. You’ll go a long way if you can look at HDL and visualize the circuit that will likely be synthesized.
There are many times where I will sketch a small schematic of gates, FFs, etc, to help visualize the functionality, then I describe the hardware in HDL. Or, I’ll sketch a timing diagram and do the same. They should all eventually become equivalent ways to accomplish a result.