New Horizons observations suggest that CH4 on Pluto has a complex history, involving reservoirs of different composition, thickness and stability controlled by volatile processes occurring on different timescales. In order to interpret these observations, we use a Pluto volatile transport model able to simulate the cycles of N2 and CH4 ices over millions of years. By assuming fixed solid mixing ratios, we explore how changes in surface albedos, emissivities and thermal inertias impact volatile transport. This work is therefore a direct and natural continuation of the work by Bertrand et al. (2018), which only explored the N2 cycles. Results show that bright CH4 deposits can create cold traps for N2 ice outside Sputnik Planitia, leading to a strong coupling between the N2 and CH4 cycles. Depending on the assumed albedo for CH4 ice, the model predicts CH4 ice accumulation (1) at the same equatorial latitudes where the Bladed Terrain Deposits are observed, supporting the idea that these CH4-rich deposits are massive and perennial, or (2) at mid-latitudes (25{deg}N-70{deg}N), forming a thick mantle which is consistent with New Horizons observations. In our simulations, both CH4 ice reservoirs are not in an equilibrium state and either one can dominate the other over long timescales, depending on the assumptions made for the CH4 albedo. This suggests that long-term volatile transport exists between the observed reservoirs. The model also reproduces the formation of N2 deposits at mid-latitudes and in the equatorial depressions surrounding the Bladed Terrain, as observed by New Horizons. At the poles, only seasonal CH4 and N2 deposits are obtained in Plutos current orbital configuration. Finally, we show that Plutos atmosphere always contained, over the last astronomical cycles, enough gaseous CH4 to absorb most of the incoming Lyman-flux.