Recycling of waste in the paving construction industry is vital for sustainability. In view of fast depleting natural stone resources, waste material in the form of recycled concrete aggregate (RCA) has been utilized in bituminous paving mixes replacing conventional coarse aggregates. Keeping in mind the inherent porous characteristics of RCA, an attempt has been made in this study to develop bituminous mixes by first pretreating RCA with locally and easily available low-viscosity material, such as bituminous emulsion. Further, steps have been taken to use waste polyethylene collected from milk packaging (WPMP) as a modifier to improve the engineering properties of bituminous paving mixes prepared involving dry process. In this work, for the purposes of comparison, dense-graded bituminous macadam (DBM) mixes were prepared using pretreated RCA (PRCA), RCA, or natural aggregate (NA) as coarse aggregates with cement as filler, each one being also modified by waste polyethylene. These mixes thus developed have been evaluated in terms of various engineering properties. It was observed that PRCA and RCA mixes, in general, satisfy the requirements in terms of Marshall characteristics and moisture susceptibility. Further, from other tests considered for evaluation, the mixes containing PRCA and WPMP showed much more superior results compared with normal mixes prepared with conventional aggregates.