Authentication protocols for authenticating devices to a server
"The problem I face is that all authentication protocols require

some kind of shared secret between the devices and the server."

Similarly, the problem I face is that $\:1 = 0 \;\;$.

Since your post includes "(eg: a digital signature of a random string by the server)", I will assume

that the server has a signature key-pair and the devices alrady know that pair's verification key.

To start, the device generates a signature key-pair $\:\langle vk_{\hspace{.02 in}d}\hspace{.02 in},sk_{\hspace{.02 in}d}\rangle\:$, $\;$ and sends $vk_{\hspace{.02 in}d}$ to the server.

When it receives a value $vk_{\hspace{.02 in}d}$, the server generates a random value $\:\operatorname{token}\:$, $\:$ sends that along with

a signature on the pair $\:\langle vk_{\hspace{.02 in}d}\hspace{.03 in},\operatorname{token}\rangle\:$ to the device, and stores $\:\langle \text{current_time}\hspace{.02 in},\hspace{-0.02 in}\text{token}\hspace{.02 in},\hspace{-0.02 in}vk_{\hspace{.02 in}d}\rangle\:\:$.

The device tests the signature. $\:$ If the signature verification algorithm accepts, then

the device displays $\:\operatorname{token}\:$ and the user manually authenticates that value to the server.

When a value is manually authenticated to the server, it deletes all triples whose left entry is too old, where "too old" depends on how many triples there are, and for each remaining

triple whose middle entry was just manually authenticated, the server stores $\langle vk_{\hspace{.02 in}d}\hspace{.02 in},\hspace{-0.02 in}\text{context_from_the_manual_authentication}\rangle\:$ and then

deletes that triple and accepts the device as authenticated.

The server also deletes the oldest triple(s) whenever the list of

triples gets too long or the left entry in those triples is way too old.

Subsequently, messages from the device to the server can be signed with $sk_{\hspace{.02 in}d}$ and verified with $\hspace{.01 in}vk_{\hspace{.02 in}d}\hspace{.02 in}$.