How to deprecate a function used in a plugin?

In addition to the answer by @Welcher:

There are some good “graveyard” examples in the core, where “functions come to die“.

You could use them as guidelines, e.g. regarding the documentation.

Here’s one such example for the permalink_link() under the wp-includes/deprecated.php

/**
 * Print the permalink of the current post in the loop.
 *
 * @since 0.71
 * @deprecated 1.2.0 Use the_permalink()
 * @see the_permalink()
 */
function permalink_link() {
        _deprecated_function( __FUNCTION__, '1.2', 'the_permalink()' );
        the_permalink();
}

Here’s the inline documentation for the _deprecated_function function that explains the input arguments:

/**
 * Mark a function as deprecated and inform when it has been used.
 *
 * There is a hook deprecated_function_run that will be called that can be used
 * to get the backtrace up to what file and function called the deprecated
 * function.
 *
 * The current behavior is to trigger a user error if WP_DEBUG is true.
 *
 * This function is to be used in every function that is deprecated.
 *
 * @since 2.5.0
 * @access private
 *
 * @param string $function    The function that was called.
 * @param string $version     The version of WordPress that deprecated the function.
 * @param string $replacement Optional. The function that should have been called. 
 *                            Default null.
 */