I had same issues and I didn't take separate regulator too seriously, which was mistake.
So I made it work using
a. separate voltage regulator
b. capacitor cca 2uF between + and - pins on NRF24
c. using RF24_PA_MAX
d. another device was about 2 meters away
Before that I had only capacitor, and when I put voltage regulator it worked for me.
I took power from arduino nano (+5V pin). No need for separate power. Powering Arduino Nano over USB is fine.