How to implement the factory method pattern in C++ correctly

First of all, there are cases when object construction is a task complex enough to justify its extraction to another class.

I believe this point is incorrect. The complexity doesn’t really matter. The relevance is what does. If an object can be constructed in one step (not like in the builder pattern), the constructor is the right place to do it. If you really need another class to perform the job, then it should be a helper class that is used from the constructor anyway.

Vec2(float x, float y);
Vec2(float angle, float magnitude); // not a valid overload!

There is an easy workaround for this:

struct Cartesian {
  inline Cartesian(float x, float y): x(x), y(y) {}
  float x, y;
};
struct Polar {
  inline Polar(float angle, float magnitude): angle(angle), magnitude(magnitude) {}
  float angle, magnitude;
};
Vec2(const Cartesian &cartesian);
Vec2(const Polar &polar);

The only disadvantage is that it looks a bit verbose:

Vec2 v2(Vec2::Cartesian(3.0f, 4.0f));

But the good thing is that you can immediately see what coordinate type you’re using, and at the same time you don’t have to worry about copying. If you want copying, and it’s expensive (as proven by profiling, of course), you may wish to use something like Qt’s shared classes to avoid copying overhead.

As for the allocation type, the main reason to use the factory pattern is usually polymorphism. Constructors can’t be virtual, and even if they could, it wouldn’t make much sense. When using static or stack allocation, you can’t create objects in a polymorphic way because the compiler needs to know the exact size. So it works only with pointers and references. And returning a reference from a factory doesn’t work too, because while an object technically can be deleted by reference, it could be rather confusing and bug-prone, see Is the practice of returning a C++ reference variable, evil? for example. So pointers are the only thing that’s left, and that includes smart pointers too. In other words, factories are most useful when used with dynamic allocation, so you can do things like this:

class Abstract {
  public:
    virtual void do() = 0;
};

class Factory {
  public:
    Abstract *create();
};

Factory f;
Abstract *a = f.create();
a->do();

In other cases, factories just help to solve minor problems like those with overloads you have mentioned. It would be nice if it was possible to use them in a uniform way, but it doesn’t hurt much that it is probably impossible.