With adjectives ending in -al it is quite common to form compounds with another word as the second word (sometimes with a hyphen between, sometimes as one word) and replace the -al of the first word with -o. One obvious example you've given already is spatio-temporal. Here are some more:
medical - medicolegal
social - sociobiology
glacial - glaciotectonic
medial - mediofrontal
dental - dentolabial
central - centrophilic/centrodorsal
ventral - ventronasal
political - politico-administrative/politicohistorical
facial - faciobrachial
nasal - nasotracheal
cortical - corticosteroid
lateral - laterocranial
visual - visuocognitive
This doesn't only happen with -al ending words, anarcho-syndicalism is the only one that comes to my mind right now.
In your case of spatiotemporal, I think your Google search result frequencies are a good start. Google NGram Viewer might have been handy for this, but it doesn't recognize hyphens or punctuation generally.
Other than that, you can check dictionaries:
American Heritage Dictionary, Collins, Random House Unabridged, Merriam-Webster, Oxford Living Dictionaries and Wiktionary all recognize spatiotemporal, with only one of them having a hyphen. It seems to be a widely accepted word. I don't know what your Word spell checker is doing, whether it's checking each individual part of the compound construction and finds that "spatio" is not a word, or whether it checks against "spatio-temporal" and does not recognize it. This wouldn't surprise me as most dictionaries that have that word list it unhyphenated.
Also, the word spatiotemporal is likely to be used within specific scientific or academic contexts, so I'd search for this term and see whether it's popularity is strong enough to satisfy you of whether you want to use it or not. I personally would not hesitate to use it. As to whether there is an American preference to use spatial-temporal instead, I'm not sure. All I know is both American and non-American dictionaries recognize "spatiotemporal".