The concentrated popularity distribution of video files and the caching of popular files on users and their subsequent distribution via device-to-device (D2D) communications have dramatically increased the throughput of wireless video networks. However, since popularity distribution is not time-invariant, and the files available in the neighborhood can change when other users move into and out of the neighborhood, there is a need for replacement of cache content. In this work, we propose a practical and feasible replacement architecture for base station (BS) assisted wireless D2D caching networks by exploiting the broadcasting of the BS. Based on the proposed architecture, we formulate a caching content replacement problem, with the goal of maximizing the time-average service rate under the cost constraint and queue stability. We combine the reward-to-go concept and the drift-plus-penalty methodology to develop a solution framework for the problem at hand. To realize the solution framework, two algorithms are proposed. The first algorithm is simple, but exploits only the historical record. The second algorithm can exploit both the historical record and future information, but is complex. Our simulation results indicate that when dynamics exist, the systems exploiting the proposed designs can outperform the systems using a static policy.