Nicolas is a nice chain store that sells wine and other alcohol.
The staff is great and most will speak some English
Just ask them for a recommendation and tell them the price you would like to pay. 20 euros should buy you a very nice bottle of wine.
there are several around Paris and this link will show you the ones close to Place Vendome.
Remember to bring a bottle opener with you.
http://www.nicolas.com/fr/nosmagasin...e_carte_google