Solved the bug this week! 
It was regarding the protocol / schema and hostname I had chosen for the app.
These are set in the capacitor.config.ts file and the documentation can be found here: Capacitor Configuration | Capacitor Documentation. The default hostname is localhost; and the default schema is capacitor on iOS and http on Android.
For simplicity, I customised these to capacitor://localhost for both iOS and Android. It has been that way since the app was launched in April 2023 and worked perfectly fine.
Approximately 4 weeks ago, Android was no longer cool with this! 
I am still looking into the facts of the matter, so if anyone knows the reason for this, please let me know.
I have now set the schema for Android to https which satisfies both Android and our Public API.
You cannot use https/http on iOS because it āCanāt be set to schemes that the WKWebView already handlesā (Capacitor Configuration | Capacitor Documentation).
The error manifested in a Redux Saga performing a history push, reporting as DOM Exception, Failed to execute 'pushState' on 'History': A history state object with URL [...] cannot be created in a document with origin [...] and URL [...].
There was a knock on effect from making this change regarding Deep Links: Android preferred me to use the App ID (e.g. com.app.my) for linking from the browser to the app. With the former, Chrome kept asking how the user would prefer to open the URL (i.e. with the app or Chrome, and ājust onceā or āevery timeā).
Thus, I now use Capacitor Device API (Device Capacitor Plugin API | Capacitor Documentation) as needed in my app to handle the differences.
When I find out the root cause, I will update this thread.
Thanks and happy coding!