Sem marcadores, o regexp (parte direita) pode corresponder a qualquer parte da string. Então, sua variante corresponde a 1234
.
Para satisfazer os requisitos, você precisa usar marcadores:
[[ "1234+5678" =~ ^[0-9]+(\s*(\-|\*)\s*[0-9]+)*$ ]] ; echo $?
E mais curto (se você quiser):
[[ "1234+5678" =~ ^[0-9\ *-]+*$ ]] ; echo $?