Understanding add_rewrite_rule

A basic rule that would work for your example:

function wpd_foo_rewrite_rule() {
    add_rewrite_rule(
        '^foo/([^/]*)/?',
        'index.php?pagename=$matches[1]&param=foo',
        'top'
    );
}
add_action( 'init', 'wpd_foo_rewrite_rule' );

This takes whatever comes after foo/ and sets that as pagename for the query, and then param gets the static value foo. If you need different URL patterns, you’ll need extra rules for each unique pattern. Refer to WP_Query docs for the various query vars that can be set within rewrite rules. Don’t forget to flush rewrite rules after adding new ones. This can be done by visiting the Permalinks Settings page.

Now visiting your example URL:

http://domain.com/foo/my_page

will load the correct page, but it’s not going to behave exactly like visiting:

http://domain.com/my_page?param=foo

because when using internal rewrites, param is set within the $wp_query query object, not the $_GET superglobal. If you need to work with code that’s looking for a value in $_GET, you’ll need an extra step to set that value:

function wpd_foo_get_param() {
    if( false !== get_query_var( 'param' ) ){
        $_GET['param'] = get_query_var( 'param' );
    }
}
add_action( 'parse_query', 'wpd_foo_get_param' );

Another method to consider is using endpoints, so /foo/ would be on the end of URLs rather than as a prefix. The advantage to this is that the API’s add_rewrite_endpoint simplifies adding all of the rules you need, including enabling pagination.