Given these constants, will SQL Server always produce the same plan for a given query? If not, are there other considerations? Is there also an element of nondeterminism to consider as well?
Query compilation is deterministic as far as I am aware. One of the original QO design goals was that it should be possible to reproduce execution plans on a different system using a statistics-only copy of the database. There are a couple of subtleties to that, around configuration parameters like the amount of memory available, and the number of logical processors, but these are covered by your list of things to synchronize.
Caveat: That is true provided the word 'same' in your list is taken to mean exactly the same in all respects. For example, the 'same' statistics might exist on the two systems, but they are only exactly the same if the histogram steps and density information are identical.
That said, the optimization process is also extremely complex, meaning it can be difficult to ensure that all inputs to this deterministic process are identical, and that all internal states are similar enough to ensure the same code path is taken through the optimizer for a particular compilation. If the query contains access outside the database (to another database or instance), those environments must be identical too.
One thing I would add to your list is to check that any plan guides also exist in the second database.
The use of non-deterministic functions like
GETDATE() in queries might mean you get a different plan too. While the main optimizer does not use the value directly, cardinality estimation can (see Constant Folding and Expression Evaluation During Cardinality Estimation). I am unsure if this class of difference falls within the scope of the question though, because both systems would produce the same plan if executed at the same time (or, more generally, with the same input variables, parameters, and function values).