I used 120k Delta miles last summer to fly JFK-CDG (Stop)-SEZ-CDG-JFK all in business class. Pay with miles will cost you three times that for coach.
I had no issues finding availability 4 months in advance. AF opens up even more as the date approaches. Then again, SFO-CDG is harder to find than JFK/EWR- CDG.
Check out my trip report for more info:
Intro
JFK-CDG
Park Hyatt Paris
CDG-SEZ
Seychelles/ Le Meridien Barbarons
SEZ-CDG
CDG-JFK