As noted in the Phase 2 post:
The Navigation block will be accessed from within wp-admin menu screen. Take a look at the mockup below which was presented in State of the Word 2018.

We'll need to determine if these mockups are the right solution. Let's dig in!
If the wp-admin menu editor is to remain non-visual, then I think the little plus icon should have some text displayed next to it saying "Add menu item" (or something similar) for accessibility reasons. No reason to leave the button unlabeled when there is plenty of space to label it and no reason to keep it small like in a standard block/post editor where you're trying not to obscure a near-preview of the front-end. In this mockup, I think the plus icon looks a bit out-of-place, given the style of the menu item metaboxes/widgets/whatever-you-call-them.
If the wp-admin menu editor is becoming more WYSIWYG, however, then that's a whole other story.
Not clear to me what happens to the menu items expandable "panels". Will they be re-implemented in React or stay as now?
There's a lot of visually hidden information there for screen reader users, things like:
aria-label="Hello world!. Menu item 2 of 2."
aria-label="Page Image Alignment. Sub item number 2 under Hello world!."
Also, the only way to reorder items when using a keyboard is by using the controls within the panels:

Why are we putting resources into the wp-admin version of menus? It seems like this would be a good opportunity to finally deprecate this screen entirely in favor of the customizer. We have taken several steps in that direction in recent years. See https://make.wordpress.org/core/2015/06/03/feature-plugin-merge-proposal-menu-customizer/ for the original formal proposal to do so. And also, numerous other updates over the years at https://make.wordpress.org/core/?s=menu+customizer.
Menus in the customizer have already been rewritten into a JavaScript-based and scalable experience. The updates there should be able to extend that existing API rather than doing a complete rewrite, unlike in the menus screen. The wp-admin menus screen largely exists as a no-js fallback at this point, which likely wouldn't be able to be maintained with blocks.
Focusing on one version of this interface, preferably the more-modern one, which already supports instant live preview, would allow more resources to ensure that this "blockification" also improves the longstanding issues with menu accessibility and extensibility.
The customizer is not fully accessible. The admin menus screen is the only place where persons with accessibility needs have a chance to build menus without having to face big accessibility barriers.
This would be a great opportunity to re-imagine the customizer UI structure to be fully accessible. That way, menus and widgets can be fully accessible without requiring maintenance of a separate accessibility mode or with a separate screen. And the other features that are only available in the customizer would get the same accessibility improvements.
If the resources that would otherwise be allocated to a new version of menus (and widgets) in wp-admin were instead focused on fixing accessibility issues in the customizer (likely via some fundamental markup changes), users would benefit from the improved accessibility for all of the functionality in the customizer. And core would no longer need to spend time maintaining (or neglecting) multiple interfaces for the same feature.
Closing this as we are now exploring here: https://github.com/WordPress/gutenberg/issues/19170