Preliminary caveat: the un-clonability of your NFC tags is relative. A mobile phone with NFC is all it takes to read one, perhaps surreptitiously. Then a number of devices like proxmark3 can emulate it. A static digital signature would not prevent that.
- Can I use a digital signature in order to tell if a given NFC-Tag belongs to my devices and if the parameters haven't been changed by an evil user?
No, a digital signature can't authenticate the data in that size-constrained tag: more memory is required that the tag allows.
All digital signatures schemes add at the very least $2b$-bit of data for $b$-bit security, so for 80-bit security (which is NOT safe enough by modern standards) we are talking 20 bytes, more than the question quotes. And that's for some BLS signature schemes pushing things to the max, which (although reportedly used with great success) have not their security strongly vetted. The industry standard is $b=128$-bit security with $4b$-bit signature, thus 64 bytes (e.g. Ed25519). I know nothing well-seasoned below $3b$-bit overhead for small signed data, or $2b$-bit for larger data (above about 220 bytes).
- I'm using an 8-bit microcontroller with very limited resources on the NFC-Reader side for the verification process. Therefore the verification step should be as easy as possible (signing the tags can be done on a powerful PC). Which Algorithm would you use for this application?
Among common signature schemes, only RSA and Rabin signature have fast verification (seconds) on 8-bit microcontrollers, but unfortunately their minimal data requirement is like 2048-bit (256 bytes) for modern security. Thus you'd need 256 bytes of memory in the tag for the signature (in addition to the UUID; the rest may come for free, see below).
With RSA/Rabin per ISO/IEC 9796-2 using SHA-256, it is possible to embed payload data into the signature (e.g. up to 222 bytes for 256-byte signature), and this payload becomes available as a byproduct of signature verification, which is fast. That's RSA/Rabin signature with message recovery. It essentially achieves $2b$-bit size overhead for $b$-bit security, for a payload at least a certain size.
All common signature schemes requiring less memory are considerably slower for signature verification, in the order of a minute for 128-bit security given the low-end CPU.
Feasible options include (not exclusive, not limitative)
- Using a Message Authentication Code rather than a digital signature. That solves the size and speed issues (8 bytes and a tenth of second is ample), but unfortunately a verification device contains the secret key that also allows to compute a MAC that makes a tag working. If an adversary can get hold of a verification device, these might need to be tamper-proof, thus slightly more expensive. And it can't be entirely ruled out that a verification device is successfully attacked and its secret key extracted (though that can be made extremely hard, even certified so).
- Going online: the UUID can be used as index in a server, knowing if the tag is registered or not. The server can digitally sign that it vets the tag with that UUID as OK, and it can use a system with lightweight signature verification. That has the advantage of allowing a dynamic black/whitelist.
