The generation of synthetic natural gas from renewable electricity enables long-term energy storage and provides clean fuels for transportation. In this article, we analyze fully renewable Power-to-Methane systems using a high-resolution energy system optimization model applied to two regions within Europe. The optimum system layout and operation depend on the availability of natural resources, which vary between locations and years. We find that much more wind than solar power is used, while the use of an intermediate battery electric storage system has little effects. The resulting levelized costs of methane vary between 0.24 and 0.30 Euro/kWh and the economic optimal utilization rate between 63% and 78%. We further discuss how the economic competitiveness of Power-to-Methane systems can be improved by the technical developments and by the use of co-products, such as oxygen and curtailed electricity. A sensitivity analysis reveals that the interest rate has the highest influence on levelized costs, followed by the investment costs for wind and electrolyzer stack.