Compiling the plocate binary from sources and then storing it in a 'bin' directory for use should be simple (including precompiled blobs would be rejected if you ever wanted to include this in the LE binary add-on repo). The sources use the meson build system and important things like specifying a non-standard DB location at compile-time appear to be supported already. If the add-contains compiled binaries I don't think script.plocate.search is correct naming (script.* is really reserved for things that are only scripts; normally Python scripts). Something like tools.plocate would be more appropriate. There is no need to have the binary built separately from the add-on; we only do that for e.g. add-ons like "System Tools" and "Multimedia Tools" where multiple separate binaries are being packaged.
LE supports udev rules being overlaid from /storage/.config/udev.rules.d at boot time, so the add-on can run a setup (b)ash script that detects presence of a known-name .rules file and create it if missing, but as you noticed there is no "uninstall" function in add-ons so if the add-on is removed the rules file becomes orphaned. You can probably add some udev logic to check for presence of the add-on bin directory first, and if not found skip the rule so orphaned rules files do no harm. It's messy though, so:
Or you can use a systemd service to run a script that creates or updates the DB before Kodi starts. The negative: using systemd not udev means you lose the ability to trigger an update to the database when a USB drive containing media is connected. The positive: you have simple systemd packaging that aligns with how most binary add-ons are already being started/stopped and packaged for LE use (so lots of prior art in our buildsystem). IMHO most users with portable USB drives full of media will have them connected to their HTPC device before boot so the loss of the connect drive feature isn't such a big deal. NB: plocate also ships with an example systemd service so you can use that with a minor tweak (the buildsystem can patch the sources) to add a kodi.target dependency.