Brace expansion with $@ arguments

You can use:

command "${@/#/foo}" "${@/#/bar}"

This uses the substitute variant of shell parameter expansion. The # anchors the match to the start of the parameter.

$ set -- a abc xyz
$ echo command "${@/#/foo}" "${@/#/bar}"
command fooa fooabc fooxyz bara barabc barxyz
$

Is there a way to scale this for larger {foo,bar,baz,...}$@ or {foo,bar}{123,456}$@?

Yes, but you would end up using arrays:

$ set -- a abc xyz
$ args=( "$@" )
$ for prefix in foo bar baz who why; do prefixed1+=( "${args[@]/#/$prefix}" ); done
$ echo command "${prefixed1[@]}"
command fooa fooabc fooxyz bara barabc barxyz baza bazabc bazxyz whoa whoabc whoxyz whya whyabc whyxyz
$

Or (noting that you have to get the sequencing correct):

$ for prefix in 123 456; do prefixed1+=( "${args[@]/#/$prefix}" ); done
$ for prefix in foo bar; do prefixed2+=( "${prefixed1[@]/#/$prefix}" ); done
$ echo command "${prefixed2[@]}"
command foo123a foo123abc foo123xyz foo456a foo456abc foo456xyz bar123a bar123abc bar123xyz bar456a bar456abc bar456xyz
$

Note that this preserves spaces in arguments:

$ unset prefixed1 prefixed2
$ set -- 'a b' 'x y z'
$ args=( "$@" )
$ for prefix in 'p p-' '123 456 '; do prefixed1+=( "${args[@]/#/$prefix}" ); done
$ echo command "${prefixed1[@]}"
command p p-a b p p-x y z 123 456 a b 123 456 x y z
$ for prefix in 'foo 1-' 'bar 2-'; do prefixed2+=( "${prefixed1[@]/#/$prefix}" ); done
$ echo command "${prefixed2[@]}"
command foo 1-p p-a b foo 1-p p-x y z foo 1-123 456 a b foo 1-123 456 x y z bar 2-p p-a b bar 2-p p-x y z bar 2-123 456 a b bar 2-123 456 x y z
$ printf "[%s]\n" "${prefixed2[@]}"
[foo 1-p p-a b]
[foo 1-p p-x y z]
[foo 1-123 456 a b]
[foo 1-123 456 x y z]
[bar 2-p p-a b]
[bar 2-p p-x y z]
[bar 2-123 456 a b]
[bar 2-123 456 x y z]
$

And the first loop could be:

for prefix in 'p p-' '123 456 '; do prefixed1+=( "${@/#/$prefix}" ); done

without using the ${args[@]} array.