In Android, How can I avoid the onStart method from being deprecated?

Use onStartCommand().

It you want to know more about how they change it, refer to google documentation like below.

// This is the old onStart method that will be called on the pre-2.0
// platform.  On 2.0 or later we override onStartCommand() so this
// method will not be called.
@Override
public void onStart(Intent intent, int startId) {
    handleStart(intent, startId);
}

@Override
public int onStartCommand(Intent intent, int flags, int startId) {
    handleStart(intent, startId);
    return START_NOT_STICKY;
}

You can use like this with onStartCommand().

package htin.linnzaw.service;

import android.app.Service;
import android.content.Intent;
import android.media.MediaPlayer;
import android.os.IBinder;
import android.widget.Toast;

public class MyService extends Service
{
    private MediaPlayer mediaplayer;
    public MyService()
    {

    }

    @Override
    public IBinder onBind(Intent intent)
    {
        // TODO: Return the communication channel to the service.
        throw new UnsupportedOperationException("Not yet implemented");
    }

    @Override
    public void onCreate()
    {
        Toast.makeText(this, "Service created", Toast.LENGTH_SHORT).show();
        mediaplayer = MediaPlayer.create(this, R.raw.eventually);
        mediaplayer.setLooping(false);
    }

    @Override
    public int onStartCommand(Intent intent, int flags, int startid)
    {
        Toast.makeText(this, "Service  Started", Toast.LENGTH_SHORT).show();
        mediaplayer.start();
        return startid;
    }

    @Override
    public void onDestroy()
    {
        Toast.makeText(this, "Service stopped", Toast.LENGTH_SHORT).show();
        mediaplayer.stop();
    }
}