As mentioned in a comment, Apple makes the source code of its versions of these tools available. Many common commands are in the "shell_cmds" package, while paste and sed are in "text_cmds". You can get the source code and compile.
Virtually all of them work fine on Linux systems, although you often have to jump into the source and remove explicitly FreeBSD-specific tests, particularly the __FBSDID("..."); line which is in almost every file. I don't know of any distribution that packages those up. Many distributions do package BSD versions of some common tools, which are very close (often identical) to the OS X versions, although they don't usually include things like paste and sed. For example, Debian includes eight packages called bsdX (none of which have either of those commands). For Apple's versions specifically, or for the many tools that aren't included in those, they're not hard to build yourself when you need them from the instructions above.
All of that said, the common subset of GNU and BSD tools is the POSIX specification, where all the basic commands are defined. You can look up the paste command or sed and see which arguments it is guaranteed to accept everywhere. This is the "morally correct" way of writing portable code: both GNU tools and BSD tools have extensions, but if you stay within POSIX your code will work on both. So check that you're always using only POSIX arguments and then what you say should work on OS X and other systems equally.
