How to obtain page breadcrumb based on menu structure only?

@Milo's code is a good baseline, but I ran in to two issues:

• It relies on the menu name as specified under Appearance → Menus. If this name ever gets changed, it would also need updated in the theme files.
• If no matching menu is found, you probably don't actually want a message "Menu not found" output for your users.

I've updated the code with the following improvements:

• Added another helper function that retrieves a menu name based on a provided location. This will prevent the first issue I listed.
• Changed the "Menu not found" message to be a PHP warning with a more detailed description
• Reformatted code to be a bit easier to read, with more detailed comments
• Modernized a few aspects of code (also changed some stuff to my own preference)
• Added typecasting where possible
• Added ability to specific separator and classes
• Returned the value instead of echoed it (easier for conditional checks)

/**
 * Retrieve a menu title from the database given the location the menu is assigned to
 *
 * @param string $location  Menu location
 *
 * @return string  The name of the menu
 */
function wpse324751_get_menu_title(string $location): string {
    $menu_name = "";

    $locations = get_nav_menu_locations();

    if (isset($locations[$location]) && $menu = get_term($locations[$location], "nav_menu")) {
        $menu_name = $menu->name;
    }

    return $menu_name;
}

/**
 * Filter through an array of menu items to locate one specific item
 *
 * @param string $field
 * @param integer $object_id
 * @param array $items
 * @return WP_Post|bool
 */
function wpse324751_get_menu_item(string $field, int $object_id, array $items) {
    foreach ($items as $item) {
        if (intval($item->$field) === $object_id) return $item;
    }

    return false;
}

/**
 * Display breadcrumbs based on a given menu
 *
 * @param string $menu_location
 * @param string $separator
 * @param string $class
 * @return string
 */
function wpse324751_nav_menu_breadcrumbs(string $menu_location, string $separator = "›", string $class = ""): string {
    /**
     * Locate all menu items of the provided menu
     */
    $items = wp_get_nav_menu_items(wpse324751_get_menu_title($menu_location));

    /**
     * If no items exist, return empty
     */
    if ($items === false) {
        trigger_error("A menu at location '" . sanitize_text_field($menu_location) . "' could not be located.", E_USER_WARNING);
        return "";
    }

    /**
     * Locate the menu item for the viewed page
     */
    $item = wpse324751_get_menu_item("object_id", get_queried_object_id(), $items);

    /**
     * If no viewed item could be located, return empty
     */
    if ($item === false){
        return "";
    }

    /**
     * Store an array of items to construct the breadcrumb
     */
    $menu_item_objects = [$item];

    /**
     * Locate all parents of the viewed item
     */
    while (intval($item->menu_item_parent) !== 0) {
        $item = wpse324751_get_menu_item("ID", $item->menu_item_parent, $items);
        $menu_item_objects[] = $item;
    }

    /**
     * Initialize array to store breadcrumbs
     */
    $breadcrumbs = [];

    /**
     * Convert menu items to links and store them in the array
     */
    foreach($menu_item_objects as $menu_item) {
        $breadcrumbs[] = sprintf("<a class='text__link link' href='%s'>%s</a>", $menu_item->url, $menu_item->title);
    }

    /**
     * Return the breadcrumbs
     */
    return "<p class='" . esc_attr(trim("text {$class}")) . "'>" . join(" {$separator} ", array_reverse($breadcrumbs)) . "</p>";
}

The wp_get_nav_menu_items function will give you an array of menu item objects for a given menu. These objects contain a mixture of data specific to that unique menu item, as well as the post/page/link data the menu item refers to. You can use this array of menu items to find the current page, and then check the parent field of the item to get each parent in a loop.

Here's an example that should get you most of the way there. Use it by calling wpd_nav_menu_breadcrumbs( 'your menu' ) in your template. Read the comments to see what's happening in each section.

// helper function to find a menu item in an array of items
function wpd_get_menu_item( $field, $object_id, $items ){
    foreach( $items as $item ){
        if( $item->$field == $object_id ) return $item;
    }
    return false;
}

function wpd_nav_menu_breadcrumbs( $menu ){
    // get menu items by menu id, slug, name, or object
    $items = wp_get_nav_menu_items( $menu );
    if( false === $items ){
        echo 'Menu not found';
        return;
    }
    // get the menu item for the current page
    $item = wpd_get_menu_item( 'object_id', get_queried_object_id(), $items );
    if( false === $item ){
        return;
    }
    // start an array of objects for the crumbs
    $menu_item_objects = array( $item );
    // loop over menu items to get the menu item parents
    while( 0 != $item->menu_item_parent ){
        $item = wpd_get_menu_item( 'ID', $item->menu_item_parent, $items );
        array_unshift( $menu_item_objects, $item );
    }
    // output crumbs
    $crumbs = array(); 
    foreach( $menu_item_objects as $menu_item ){
        $link = '<a href="%s">%s</a>';
        $crumbs[] = sprintf( $link, $menu_item->url, $menu_item->title );
    }
    echo join( ' > ', $crumbs );
}

*disclaimer: not rigorously tested, use at your own risk