@saraheagle Can you look at #44257 if its the same Issue?

Yes, it does look the same issue.
I tested it locally but when I add
'catid' => 'STRING',
as Andrew says works for him, I get the 404 error, like we did a few weeks ago.

I then tested with this old code from an old backup and it works perfectly

protected function _buildDataObject()
	{
		$data = new \stdClass;

		// Build the additional URL parameters string.
		$params = '';

		if (!empty($this->additionalUrlParams))
		{
			foreach ($this->additionalUrlParams as $key => $value)
			{
				$params .= '&' . $key . '=' . $value;
			}
		}

		$data->all = new PaginationObject(\JText::_('JLIB_HTML_VIEW_ALL'), $this->prefix);

		if (!$this->viewall)
		{
			$data->all->base = '0';
			$data->all->link = \JRoute::_($params . '&' . $this->prefix . 'limitstart=');
		}

		// Set the start and previous data objects.
		$data->start    = new PaginationObject(\JText::_('JLIB_HTML_START'), $this->prefix);
		$data->previous = new PaginationObject(\JText::_('JPREV'), $this->prefix);

		if ($this->pagesCurrent > 1)
		{
			$page = ($this->pagesCurrent - 2) * $this->limit;

			if ($this->hideEmptyLimitstart)
			{
				$data->start->link = \JRoute::_($params . '&' . $this->prefix . 'limitstart=');
			}
			else
			{
				$data->start->link = \JRoute::_($params . '&' . $this->prefix . 'limitstart=0');
			}

			$data->start->base    = '0';
			$data->previous->base = $page;

			if ($page === 0 && $this->hideEmptyLimitstart)
			{
				$data->previous->link = $data->start->link;
			}
			else
			{
				$data->previous->link = \JRoute::_($params . '&' . $this->prefix . 'limitstart=' . $page);
			}
		}

		// Set the next and end data objects.
		$data->next = new PaginationObject(\JText::_('JNEXT'), $this->prefix);
		$data->end  = new PaginationObject(\JText::_('JLIB_HTML_END'), $this->prefix);

		if ($this->pagesCurrent < $this->pagesTotal)
		{
			$next = $this->pagesCurrent * $this->limit;
			$end  = ($this->pagesTotal - 1) * $this->limit;

			$data->next->base = $next;
			$data->next->link = \JRoute::_($params . '&' . $this->prefix . 'limitstart=' . $next);
			$data->end->base  = $end;
			$data->end->link  = \JRoute::_($params . '&' . $this->prefix . 'limitstart=' . $end);
		}

		$data->pages = array();
		$stop        = $this->pagesStop;

		for ($i = $this->pagesStart; $i <= $stop; $i++)
		{
			$offset = ($i - 1) * $this->limit;

			$data->pages[$i] = new PaginationObject($i, $this->prefix);

			if ($i != $this->pagesCurrent || $this->viewall)
			{
				$data->pages[$i]->base = $offset;

				if ($offset === 0 && $this->hideEmptyLimitstart)
				{
					$data->pages[$i]->link = $data->start->link;
				}
				else
				{
					$data->pages[$i]->link = \JRoute::_($params . '&' . $this->prefix . 'limitstart=' . $offset);
				}
			}
			else
			{
				$data->pages[$i]->active = true;
			}
		}

		return $data;
	}

@saraheagle It appears to be fixed on your end. Did you use the setAdditionalUrlParam method? https://docs.joomla.org/J5.x:Pagination_class_removes_query_parameters

This site is in j4, I just used the old code (from the prev. post) temporarily as it had been broken for a few weeks.

I have just looked at the 'fix' and if I am reading it correctly, we need to add this line for each URL param that we need retained in the URL string?
$this->pagination->setAdditionalUrlParam('xxx', $state->get('xxx'));

So in this case, I need to edit a core file and check this each time I update Joomla!?
https://github.com/joomla/joomla-cms/blob/51032f65eb10bb9a78be7c264b511a933740318e/components/com_content/src/View/Category/HtmlView.php

And if my client adds a new J2Store filter, I need to amend the core file again?
It doesn't seem a very workable solution, or am I missing something?
Thanks very much for your help
S :)

It would be handled in J2Store and not modify manually the core file.

J2Store adds a new tab to Joomla articles for its product details so it uses Joomla categories. It does not have it's own products 'section' like virtuemart etc.

So any 3rd party extension that adds a new tab/form to existing articles would also suffer from this issue.

Since this is not a Joomla core bug, I'm closing this one.