Wrapping paper could work, but you'd have to be very careful with your application. You'd ideally cover one side of the prop at a time and the underside of the wrapping paper with an even coat of some kind of adhesive and CAREFULLY lay the paper down on it. But! That could get extremely messy very fast and you might end up with wrinkles in the paper/cardboard. The glue will weigh it down/soften it too, which could be a problem. You'd also ideally want to spray or paint it with some kind of protective coating, which might cause more bubbles/wrinkles/weight. The benefit is that, if you could get everything just right, the color would be very bold and even. The downside is that it's really finicky, ESPECIALLY if you end up needing to cut the paper to fit in any way, wrinkles show up in wrapping paper super clearly, and the cardboard might not hold up to the weight if it isn't several layers deep.

A much easier option would be three cans of spray paint--one primer, one color, and one top coat. The "primer color" ones are a lie and it's better to just do it in three steps. You'd prime it to give it a nice, even base to work off and make sure you can't see the brown underneath, and wait for it to dry; spray on red, and wait for it to dry; and then spray on a top coat to make it shine/protect it. Working in several lighter, even coats as opposed to one heavy coat gives a much better finish and takes a little less time, even though you think it would be the opposite. You'll also probably have some left over, which is always nice.

You could also hand-paint it with acrylic paints and then seal it with something like Modpodge if you can't get to spray paint. That gives you a lot more control, but will get very messy, will take a bit longer, and you'll probably still have to do multiple coats.

I'm totally biased because it's my go-to, but I think spray paint might be your best bet.