This study provides a novel idea for ball milling modification treatment of municipal sludge after starch coating and application to prepare paper packaging materials as papermaking fillers, which can not only solve the problem of municipal sludge treatment and disposal in our country but also alleviate the shortage of papermaking raw material. The effects of the ball-to-material ratio, ball milling time, and ball milling speed on the particle size and Zeta potential of sludge, as well as the performance of the paper packaging material, were investigated. The forming mechanism of sludge-based paper packaging material was explored through analyzing micromorphology and thermal stability. The experimental results showed that the modification by ball milling can effectively reduce the median particle size of the starch-coated sludge filler and reduce its Zeta potential. The mechanical properties of the paper packaging materials prepared from the sludge modified by starch coating were significantly improved, and the thermal stability was better. The results indicated that sludge-based paper packaging material prepared by starch coating-ball milling modification was an ideal material for packing. This study also provided a new method for the high-value application of municipal sludge.