Right now we have a trailing appender on the Gallery block which is a bit problematic — it only allows inserting new images or editing the gallery if you are at the bottom of it. On large galleries that requires scrolling. We should move these controls to the toolbar instead, which scrolls with the user.
Visuals.

Here is what it looks like for single images.

That means having somewhat similar controls for the gallery in the toolbar as exist for single image blocks.
Is this all we need? ("Current media URL" wouldn't apply at the level of the gallery.)

@mtias, should we keep the bar at the bottom with (now duplicate) Upload and Media Library buttons, or do you envision the controls at the top replacing them?
I'd hope we can replace them initially. Eventually gallery items will be blocks and we could use the actual inserter.
Gallery items will likely become nested image blocks inside a parent gallery.
That means something like this: https://github.com/WordPress/gutenberg/issues/11436#issuecomment-485347444
@dwolfe Perhaps a + icon would be more fitting than "Add" in that toolbar. I also would remove the dropdown actions in favor of just opening the media modal. What do you think?
@MichaelArestad:
+ icon would be more successful than an explicit label?In the interest of moving this forward, I think the word "Add" is clearer than an icon, and it reuses the "Replace" pattern from the image block toolbar. Also, the dropdown surfaces the option to upload a new image more clearly than the Media Library's "Add New" button, which has to compete visually with a thumbnail grid; so I think the dropdown (which also aligns with the "Replace" control) is a better compromise than immediately opening the Media Library.
I think this is good enough for now, and we can iterate based on any feedback we get once it's merged.
Updated comp incorporating @mtias' feedback above:

To summarize:
NOTE: This is a temporary fix, given that the Gallery block will at some point transition to a nested block architecture as @paaljoachim mentioned above.
Why do you think a + icon would be more successful than an explicit label?
It follows the toolbar (and inserter) paradigm. It will have a label on focus/hover like other toolbar actions. It won't take up much space (translations).
Thanks for adding rationale, @MichaelArestad. Just a couple of points:
It follows the toolbar (and inserter) paradigm. It will have a label on focus/hover like other toolbar actions.
We're already breaking that paradigm with the image block "Replace" button. We need additional clarity here also, because we're removing the trailing appender, meaning that the "Add" button in the block toolbar will be the only way to add images to a gallery. We need to do what we can to prevent users from missing it, so in this case, standing out from the other block controls is an asset, not a drawback. Hover interactions are an enhancement and nice to have, but shouldn't be required to understand the interface.
It won't take up much space (translations).
This is a good point, but less of a concern on a container block with four controls.
Again, we'll have a chance to revisit this when the gallery block becomes a container of nested image blocks. I think this solution works well enough for now.
Here is a PR for nesting of Image blocks in a Gallery block. https://github.com/WordPress/gutenberg/pull/25940
During my latest test of the PR it looked like this:

Which means (as I see it) we can remove the bottom Media Library bar as there is now an inline inserter for adding new images. Then center align the Gallery caption just below the images.
EDIT: It is being handled in this PR: https://github.com/WordPress/gutenberg/pull/25321 (mentioned just above)