Do not get a multi-effects unit just for distortion. You will regret it.
For Starlight, if you want to stay cheap, get an Ibanez PD7. It has less noise than the Boss, and to me comes closer to that tone.
For a little more money, the next pedal I would think of is the MXR Blowtorch or the Wounded Paw Attack Goat. Both are within the $140-$150 range new, and you can probably find them in the classifieds for less if you're patient.
The important thing for a song like that (and many MUSE songs) is to have a clean blend available with any pedal you might pick, at least enough to retain the natural bottom of your bass.