For any veggies at a loss in Paris, there's a great place near Hotel de Ville called La Victoire Supreme du Coeur. Their cake is particularly good. Also, try happycow for a list of restaurants in the city.
