Right time to start applying for PhD - Germany
I'd recommend that you start applying a few months before you graduate. The process may easily take several months, and if you want a direct transition, you need to find something before you actually graduate.

In most cases, it will be possible to delay the start of a position by a few months. So by all means, if you find an interesting position that starts a bit before you expect to graduate, you should still apply. Just state the date of you expected graduation (month/year is fine) with your application.

Note that many potential employers, especially if they don't know you from earlier activities, will want to see results of academic work such as a Masters thesis (or at least a draft for it) or other academic texts. If you can't show anything in that direction, it would be good to first focus on positions where you know the professor.