There are two types of searching, file name based searching and Spotlight meta-data based searching.
If you are searching a local volume or a volume shared by an Apple Mac acting as a File Server then both methods should work since the Mac will index files for searching via Spotlight and also be able to do the basic file name searching. However a NAS server like your Synology is not a Mac, it therefore runs not Apple's software but an open-source program called Netatalk. More recent versions of Netatalk do include a feature allowing them to index the files for use with Spotlight but not all NAS devices have a new enough version and even those that do may not have enabled this feature.
I believe Synology devices running DSM 6.0 or later can do Spotlight indexing, so in theory you are covered. This is likely to only work via an AFP connection, while you say you have enabled AFP access you need to make sure your El Capitan running Macs are actually connecting via AFP. This is because depending on how you connect to a server El Capitan will normally pick SMB rather than AFP to connect with.
Rather than clicking on the name of the Synology server in the lefthand sidebar of a Mac Finder window, or via the Browse Network window, instead you must use the 'Connect to Server' dialog box and type in afp://address.of.server
By including the afp:// at the beginning of the address you tell OS X to only use AFP.
In theory if Spotlight is not available the Mac should revert to a simple filename only based search which obviously should find files if their names exist. If file and folder permissions prevent you accessing some files or folders then they should not be listed. If the Mac is using Spotlight but Spotlight is returning incomplete results then either - in this case on the Synology the indexing process has not finished, or the indexing process also does not have permission to access some files/folders or the spotlight index is corrupt. If the later you need to somehow force it to redo the indexing from scratch. (This is sometimes necessary on a genuine Mac server let alone one that is not a real Mac.)