How long before PhD graduation should I start applying for post-doc positions?

It depends on the type of funding associated with the postdoc position:

1) If the funding is already there and has a limited duration (for instance a one-year funding within a one-year research project), then indeed, the recruiter might not want to wait 10 months for you, since it would mean that an important part of the funding might be "wasted".

2) If the funding is already there, but can be used later on (for instance a one-year funding within a five-year research project), then it could be possible to start only in 10 months.

3) If there is no funding yet, and you need to get it yourself, then you have to start as early as possible, since it can take a long time for the whole process to finish.

Note that case 3 is usually a process you started with a potential advisor, rather than answer to a particular announcement. In any case, it's always a good thing to informally contact potential advisors directly to see about the specificity of a particular position.

It doesn't hurt to apply. Sure, in some cases the hosting institutions might want to consider someone with a definite graduation date, but that's their decisions. It could also be that the hosting institution loves you and is willing to wait until whenever you are done, given that the funding will be available later still (I have seen one case like this). Just be honest/realistic about when you expect to graduate. Post-doc positions are pretty competitive these days and it is better to look for more options than less.

If you are not comfortable applying formally early on, then at least make sure to use your informal contacts so that they know you are actively looking.

Positions are often advertised on an extremely short notice, at least in my field (computer science). So applying much ahead of the graduation is not strictly necessary in my opinion.

Other positions are not (yet) advertised (e.g. the PI has some money and considers whether to pay for 2 PhDs or one postdoc etc). For those it is more important to be in some exchange with people in the field: typically through conferences/workshops; but also 'boring' project meetings organized by funding agencies are good opportunities to network. Other ideas include: contributing useful software to the community, internships, giving talks at other universities when you are traveling, etc...

If you do some of this, you will not have difficulty finding a postdoc position. Your application will only be a formality, after everything else is already decided.

Also, why not have a break after the PhD? Traveling the world? Decide for yourself for some while what to do with your time?

In my experience, employers both in academia and industry want good candidates to start rather earlier than later, and are often not planning far ahead with their personnel decisions.