menu item to display the most recent post

If you want to perform any redirects, you have to send your header before site sends any output.

Shortcodes are run when the content is obtained, parsed and printed. So the site will already be partially sent to the browser, so you won’t be able to perform any redirects any more.

So you should run your code using some hook that is fired before any output is sent to the browser. You can use wp hook for example.

And if you really want the shortcode to cause redirection, then:

1. Display a link instead – it will be less confusing for users, I guess.
2. You’ll have to do the redirection in JS:

.

function get_latest_post( $atts) {
    extract( shortcode_atts( array(
        'cat' => '',
    ), $atts, 'latestpost' ) );

    $args = array(
        'posts_per_page' => 1, // we need only the latest post, so get that post $
        'cat' => $cat, // Use the category id, can also replace with category_nam$
        //'category_name' => 'SLUG OF FOO CATEGORY,
    );
    $q = new WP_Query( $args);
    if ( $q->have_posts() ) {
        while ( $q->have_posts() ) {
            $q->the_post();

            // Your template tags and markup like:
            // the_title();
            $link=get_permalink($post);
            // echo $link;
            // echo $cat;
            echo '<script type="text/javascript>document.location.href = "' . $link . '";</script>'
            return;  // you want only one redirection in your site
        }
        wp_reset_postdata();
    }
}
add_shortcode( 'latestpost', 'get_latest_post' );