PWM frequency and sine waveform generation
Secrets of Arduino PWM should answer most of your questions but you might need to read it a couple of times. It says:


  Each of the timers has a prescaler that generates the timer clock by dividing the system clock by a prescale factor such as 1, 8, 64, 256, or 1024. The Arduino has a system clock of 16 MHz and the timer clock frequency will be the system clock frequency divided by the prescale factor. Note that Timer 2 has a different set of prescale values from the other timers.


That means that you are limited in the chosen value. You can get the PWM counters to reset at a value lower than 256 but then you lose PWM resolution.


  As I understood, it is possible to choose an arbitrary frequency (with some limits obviously) since it is determined by some settings on the MCU internal timers. How do we choose it? Does its choice depend on the low - pass filter we decide to apply?


The first sentence is correct as discussed already.



Figure 1. PWM for sinewave generation. Note that the PWM waveform is shown as a relatively low frequency for illustrative purposes. In practice it would need to be a couple of orders of magnitude of frequency higher than the sinewave to be produced. Source: How is a PWM signal converted to Sine using a transformer?.

The second sentence is also correct. The filter on the PWM output has to filter out all the higher frequencies of the PWM if you hope to get a smooth sine.


  Is there any method to generate the full waveform directly on a single pin?


Yes, but since the PWM is switching between 0 V and 5 V (or 3.3 V as the case may be) you have to bias the 'zero' of the sine to half supply or some other positive voltage.