How to deprecate a function used in a plugin?

I would suggest something like:

/**
 * @deprecated Please use good_function_name() instead
 * @since x.y.z Marked deprecated in favor of good_function_name()
 * @see good_function_name()
 */
function bad_function_name() {
    trigger_error(
        'The ' . __FUNCTION__ . ' function is deprecated. ' .
        'Please use good_function_name() instead.',
        defined( 'E_USER_DEPRECATED' ) ? E_USER_DEPRECATED : E_USER_WARNING
    );

    return good_function_name();
}

This has the effect of showing a deprecation warning in the logs along with a stack trace. Naturally this will only work if logging is enabled in WordPress.

The ternary operator is there because the E_USER_DEPRECATED constant was only introduced in PHP 5.3.0. In older versions we can fall back to a simple user warning instead.

From the PHP manual on error constants:

E_DEPRECATED Run-time notices. Enable this to receive warnings about code that will not work in future versions.

The reason I do not like to use _doing_it_wrong or __deprecated_function is that these functions are intended only for WordPress core. From the code reference on those functions:

This function’s access is marked private. This means it is not intended for use by plugin or theme developers, only in other core functions. It is listed here for completeness.

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.
 */

Deprecation does not always equal being removed, it usually means that the item is marked for EVENTUAL removal from the API. Is this a method that will be called externally - as in by other plugins or developers? If this method is only ever used by the plugin internally, you can probably safely remove replace it with a better name function.

If not, I'd create the better named function and have the badly named one call it with a __doing_it_wrong call - read about it in the codex This will give other developers time to update their references to the method and you can safely remove the method in a later version.

function badly_named() {

    __doing_it_wrong( 'badly_named', 'This method has been deprecated in favor of better_named_function' );

    /**
     * Call the better named method
     */
     better_named_function();
}

Hope this helps!

You create a new plugin and advice your users to migrate to it as the current one is EOL.

There is nothing more annoying than plugin and theme authors changing their public APIs and try to treat it as "just another small upgrade". There is no reason to break sites because of a problem your users are actually not being affected by.