And if there is an easy replacement, then how about re-implementing mktemp() using that replacement, instead of removing it?
Indeed. The principal security issue with mktemp is the difficulty in creating a user-specific thing under a shared /tmp folder in a multi-user setup.
But if it hurts when you use /tmp, why use /tmp? Use a path with no world-accessible ancestor, or at least no world-writable ancestor.
On Windows, that means creating it somewhere under the CSIDL_LOCAL_APPDATA folder. Which is already the default for %TEMP% and %TMP%. On Unix, it's a $HOME subfolder with access 700 or 600. How about switching mktemp over to use that?