本体のストレージが多くても、cloudの容量が少ないとバックアップ出来ない？

データ移行のためにiCloudのバックアップを使うなら、iCloudのストレージのアップグレードが必要でしょうね。

iCloudバックアップを使わずに直接移行できませんか？

クイックスタートを使って新しい iPhone、iPad、iPod touch にデータを転送する - Apple サポート

そもそも、機種変でiPhoneのストレージが増えてデータ量が増えればいずれはiCloudのストレージも増やす必要があります。バックアップを取るなら尚更です。

iPhoneのストレージ容量は増やせません。

増やしたければ買い替えしかありません。