The affected area is no longer buildable. It is no longer considered building land.
If the OP wants to build a new house exactly there, it falls under the point you mentioned and the municipal utilities will remove or relocate it free of charge. You are absolutely right about that. But not for a few trees...
We would like to plant one or two apple or cherry trees or even build a garden shed. None of this is possible because the line basically occupies half the garden. I can provide the plan later.
Most fruit trees, as far as I know, including apple and cherry trees, are not deep-rooted but shallow-rooted. Please check Google again just to be sure. With shallow-rooted trees, there should be no problems. And a garden shed is also not an obstacle, as long as you are not placing a luxury log cabin there.
Have you received a concrete rejection from the municipality? Who did you speak to? The municipality itself has relatively little say in this matter. The utility company is the right contact.
I will check this evening if I can find anything in my documents regarding this.