The solution will depend on what you want as a result.
Do you want all the new velocities to be identical or do you want them scaled relative to the original velocities.
The first scenario is easy, select your notes (as described above) and just enter the new velocity in the Event Inspector.
For the second scenario, there are at least 3 ways to accomplish this, but probably the easiest way is to simply select the notes as before, then in Track View Right Click the clip and use Process Effect > Midi Effects > Cakewalk Fx > Velocity.
This will open up the plugin where you have total control over your new velocities