Error: “Cannot modify header information”

The basic problem you have is that you want to send a redirect header, and that redirection code is executed too late, namely in your shortcode handler. You can send HTTP headers only before any output has been sent, not later.

So what you have to do, generally speaking, is separating the shortcode logic from the redirection logic.

Here is a very simple example, illustrating the general approach. Not tested!

class ShortcodeRedirect
{
    private $identifier="wpse359995";

    public function form( $atts, $content="" )
    {
        return '<form method="post" accept-charset="utf-8">' .
        $content
        '<input type="hidden" name="key" value="' . $this->identifier . '">
        <input type="text">
        <input type="submit">
        </form>';
    }

    public function redirect()
    {
        if ( 'POST' !== $_SERVER['REQUEST_METHOD'] )
            return;

        $key = filter_input( INPUT_POST, 'key', FILTER_SANITIZE_STRING );

        if ( ! $key or ( $key !== $this->identifier ) )
            return;

        $text = filter_input( INPUT_POST, 'text', FILTER_SANITIZE_STRING );

        if ( ! $text )
            return;

        wp_redirect( 'your_target_url' );
        exit;
    }
}

if ( ! is_admin() ) {
    $shortcoderedirect = new ShortcodeRedirect;

    add_shortcode( 'form', [ $shortcoderedirect, 'form' ] );
    add_action( 'template_redirect', [ $shortcoderedirect, 'redirect' ] );
}

As you can see, the shortcode callback doesn’t know anything about the HTTP headers, and the redirection callback (template_redirect is the proper hook to do that) doesn’t know anything about the shortcode.

The only connection between them is the identifier, a private property of the class, which can’t be accessed from the outside.

And if I may say so: Don’t use plugins to inject executable PHP code into your posts. This can backfire quite badly if some gets access to the post content somehow, and it’s very difficult to debug, as you have experienced already. Try to write your own code, and put that into a proper plugin. You might actually enjoy it. 🙂