(Indirectly) looking for a PhD before I have published a paper
It sounds like the visiting professor was speaking in rather vague terms, just being a nice guy offering to help you make a connection with people in your target researc area.  This is nice, and under normal circumstances you would follow up by sending a short email and with a short CV attached, since that's what he suggested; however, there is in principle nothing to prevent you from writing directly to the people the visitor had in mind.
But I think your question is more about how to apply for a PhD program, so let's look at that.
I suppose PhD applications are different in Europe than in the U.S.  In the U.S., I would say:

Today is February 19.  If you have just started your last semester of your master's program, and have no plans for next fall, then you'll have to get cracking with your PhD applications.  Meaning, drop everything and get them out the door ASAP, hoping to either barely make the submission deadline, or hoping your application will be considered after the deadline.
If you can continue on in your current department for another semester or year, then write down the application deadlines for the programs you're interested in, work backwards from that, and sit down and talk with your advisors about your timeline.  You may be able to find some programs that allow a January start date, but watch out, teaching assistantships are typically given to August start students.

I am sorry I don't know about procedures, timelines and customs for PhD admissions in Europe.  All I can suggest is that you start by carefully reading the admissions information published on the target university's website.
You could take a look at Academia SE questions related to the PhD admissions process in Europe, and ask a question targeted at that specifically.
Additional notes: in general it is best not to go against one's advisor's wishes; your question did make me wonder if your advisors are trying to keep you in your current department.