困っていたこと
既にデプロイ済みのAWS SAMスタックで、開発環境用にCORSの設定を緩める必要があって、API GatewayとLambdaのAllow-Originを*にしようとしました。（API GatewayはREST APIタイプ）
sam deployした後、マネジメントコンソールで確認してみると、リソースには変更が反映されている模様。
きちんとAllow-Originが*になっている。
リソース→アクション→CORSの有効化
解決！
先輩のアドバイスで、マネジメントコンソールでAPIを手動でデプロイしてみる。
リソース→アクション→APIのデプロイ
これでうまくいきました。
今回は問題は解決されたけど、sam deployしたのにAPI Gatewayだけ手動で再デプロイしないといけないって、一体全体どんな仕様なんだ！？
ドキュメントを見てみる
REST APIのドキュメントでは、それに近しい、下記のような注意書きが。
また、こんなドキュメントも↓
今回はマネジメントコンソールでデプロイしましたが、CLIでもできそうですね。
https://docs.aws.amazon.com/ja_jp/apigateway/latest/developerguide/set-up-deployments.html
（参考）同じことで困った方々がいらっしゃる模様。