Pagination works in custom query loop but it doesn’t work in shortcode

Hmmm…
It looks like your shortcode function defines $page, but the query itself uses $paged….with a d on the end. Maybe remove the d?
In other words, try changing

'paged' => $paged

into

'paged' => $page