Go onto Route 23, and run near a patch of grass for shaking grass & train against Audinos.
Give your Pokemon the Lucky Egg you got from Juniper to boost exp. as well.
Those Audino are 48-51, so they should be the right level for you.
Staryu should really be Starmie by now, and you don't have a solid counter for Marshall. I suggest you evolve Staryu and give it a Psychic move (Psyshock/ Psychic would be best).