以下のような画面がでてVPCの削除ができず。。。

最終的に、VPCに残っていたセキュリティグループのインバウンドルールを全て削除したらエラーが解消されました。

これは、セキュリティグループのインバウンドのソースに、別のセキュリティグループが設定されていたため、
その設定されていたセキュリティグループが依存関係のせいで削除できなかったものと思われる。