While still doing my research in order to ask the question properly, I have found three solutions. Considering how hard it was to find this information, I decided to post the question and answer here anyway.

---

1. Setting the PATH explicitly using two COMMAND parameters

The script being generated for the custom build step in Visual Studio contains some prologue, then the commands themselves and then some epilogue. Wouldn't it be possible to simply add set PATH=... before the real command through another COMMAND parameter?

The documentation for add_custom_command() says:

COMMAND
Specify the command-line(s) to execute at build time. If more than one COMMAND is specified they will be executed in order, but not necessarily composed into a stateful shell or batch script.

So no, that's not guaranteed to be possible. But the Visual Studio project generator actually does it like this, i.e. the individual commands are just appended one after another, so the following does the job:

add_custom_command(OUTPUT "${CMAKE_CURRENT_BINARY_DIR}/Table.h"
                   COMMAND set "PATH=${LibFoo_RUNTIME_LIBRARY_DIRS};%PATH%"
                   COMMAND TableGenerator "${CMAKE_CURRENT_BINARY_DIR}/Table.h"
                   DEPENDS TableGenerator)

Advantages:
▪ The PATH can be changed for each custom command explicitly

Disadvantages:
▪ Relies on an undocumented behavior of the generator
▪ It's necessary to rewrite the whole command for Windows and keep both versions in sync
▪ Each custom command must be changed explicitly

---

2. Using file(GENERATE ...) to create a custom script

The documentation for add_custom_command() quoted above continues:

To run a full script, use the configure_file() command or the file(GENERATE) command to create it, and then specify a COMMAND to launch it.

This is a bit messy because of the additional temporary files and commands:

file(GENERATE OUTPUT "${CMAKE_CURRENT_BINARY_DIR}/RunTableGenerator.cmd"
              CONTENT "set PATH=${LibFoo_RUNTIME_LIBRARY_DIRS};%PATH%
                       %1 ${CMAKE_CURRENT_BINARY_DIR}/Table.h")
add_custom_command(OUTPUT "${CMAKE_CURRENT_BINARY_DIR}/Table.h"
                   COMMAND "${CMAKE_CURRENT_BINARY_DIR}/RunTableGenerator.cmd" "$<TARGET_FILE:TableGenerator>"
                   DEPENDS TableGenerator)

Notice the awkward way of sending the path to the executable as an argument. This is necessary because the script is writen once, but TableGenerator might be in different locations for different configurations (debug and release). If the generator expression was used directly in the content, a CMake error would be printed and the project would not build correctly for all but one configuration.

Advantages:
▪ The PATH can be changed for each custom command explicitly
▪ A fully documented and recommended solution

Disadvantages:
▪ Very noisy in the CMakefiles
▪ It's necessary to rewrite the whole command for Windows and keep both versions in sync
▪ Each custom command must be changed explicitly

---

3. Using undocumented variable CMAKE_MSVCIDE_RUN_PATH

While looking at the CMake sources, I noticed there was an undocumented variable CMAKE_MSVCIDE_RUN_PATH which, if set, resulted in a line like this being added to the custom build step script:

set PATH=<CMAKE_MSVCIDE_RUN_PATH>;%PATH%

So all that's needed then is something like this at a good place:

set(CMAKE_MSVCIDE_RUN_PATH ${LibFoo_RUNTIME_LIBRARY_DIRS})

Advantages:
▪ Can be enabled at one central place
▪ No change at all in any of the add_custom_command() commands elsewhere is needed
▪ Only the path itself is set, no batch commands need to be written explicitly

Disadvantages:
▪ Global for the whole CMake project and all custom commands
▪ The variable is undocumented (therefore can get removed etc.)

---

I have personally settled on the solution #3 because it is clean and simple, hoping that it will stay. After all, it's been there for 9 years already.