EC-CUBEの4系を利用してまして、今までは購入したプラグインをダウンロードし、zipのまま手動でサーバへアップロードして
アップロード先のサーバで解凍といった手順でプラグインのインストールが行っておりましたが、いつのまにかストアでは購入したプラグインのダウンロードができなくなりました。

推奨方法はあくまでサーバがシングル構成の場合は有効かと思いますが、冗長化している環境では有効でないので今までできていた
手動でのインストールが行えないのは致命的です。

冗長化して運用している皆様はどのようにプラグインをインストールしているのでしょうか。

最悪、シングルで環境作成してファイルをインストールした後にプラグインのファイルのみをコピーして・・・
ということも可能なのでしょうが、有料プラグインの場合ですとライセンスによっては２重でお支払いしないといけなくなります。

何かいい方法があれば教えて下さい。

インストールできないのは管理画面では購入したプラグインの内容が表示されるものの、ダウンロードやインストール、歯車のアイコン等が一切表示されてないのでおそらく冗長化してある環境だと「認証キー」の判定が正常に行われないのではないかと考えています。

>冗長化して運用している皆様はどのようにプラグインをインストールしているのでしょうか。

冗長化というのが、ロードバランサを導入しWEBサーバを2台用意している、という仮定でのご回答ですが、
管理画面へのアクセスは冗長化せずにバランシング先をどちらか1つのWEBサーバにアクセス固定する形ではいかがでしょうか。

https://qiita.com/applexco/items/0f0f5b2640cc79580d29

上記URLで紹介されている方法もあります
ライセンスに関しては提供元次第なので直接訪ねるのが宜しいかと思います