Adding the '0x' to the bytecode worked for me, didn't need to reinstall the wallet provider.

const Web3 = require('web3');
const Compiler = require('./Compiler');
const HDwalletProvider = require('truffle-hdwallet-provider');
const {interface,bytecode} = Compiler.parse('Inbox');
const walletProvider = new HDwalletProvider('Mnemonic','Rinkeby_link');
const web3 = new Web3(walletProvider);

async function deploy(){
  let accounts = await web3.eth.getAccounts();
  console.log('Deploying from Contract : ',accounts[0]);
  let details = await new web3.eth.Contract(JSON.parse(interface)).deploy({data:'0x'+bytecode,arguments:['Msg for rinkeby']}).send({from:accounts[0],gas:'3000000'});
  console.log(details.options.address);
}
deploy();

Adding the '0x' to the bytecode worked for me, didn't need to reinstall the wallet provider.For some reason when I didn't add the '0x' to the bytecode, the I ended up using all the gas.

If you check https://rinkeby.etherscan.io/ and scan for the account you used to deploy, it will clearly show how much gas has been used. before the '0x' it shows that all gas was used up (3,000,000 gas), but after the '0x' is added it shows 281,572 gas has been used.

const Web3 = require('web3');
const Compiler = require('./Compiler');
const HDwalletProvider = require('truffle-hdwallet-provider');
const {interface,bytecode} = Compiler.parse('Inbox');
const walletProvider = new HDwalletProvider('Mnemonic','Rinkeby_link');
const web3 = new Web3(walletProvider);

async function deploy(){
  let accounts = await web3.eth.getAccounts();
  console.log('Deploying from Contract : ',accounts[0]);
  let details = await new web3.eth.Contract(JSON.parse(interface)).deploy({data:'0x'+bytecode,arguments:['Msg for rinkeby']}).send({from:accounts[0],gas:'3000000'});
  console.log(details.options.address);
}
deploy();