Oi Lucas, tudo bem? A questão não é a adição do novo estado e a transição de um estado para o outro, veja que o estado aprovado ou reprovado, a adição de novos estados só te força a implementar a interface EstadoDeUmOrcamento, que se não tiver uma regra associada, pode ser até mesmo um Enum, o que faria você não precisar da interface diretamente.
A questão que fica é como transitar de um estado para o outro considerando o comportamento/ação que o objeto pode ter. O orçamento neste caso pode ser aprovado, reprovado ou estar em aprovação. O comportamento da troca de estado está na interface. Se a adição do novo estado, requer que você reveja todo o fluxo de troca de estados, então o uso da interface é a melhor alternativa, por que de fato ela vai quebrar em todos os pontos que você precisa lembrar de mudar.